两次遍历
思路:
先遍历一次得到数组长度 length, 第二次遍历找到位置在 length-n 的节点 p, 让 p.next=p.next.next 即可
代码:
- # Definition for singly-linked list.
- # class ListNode:
- # def __init__(self, x):
- # self.val = x
- # self.next = None
- class Solution:
- def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
- result = ListNode(0)
- result.next = head
- length = 0
- first = head
- while first:
- first = first.next
- length +=1
- length -= n
- first = head
- for i in range(length-1):
- first = first.next
- first.next = first.next.next
- return result.next
快慢指针
两个指针距离为 n, 同时移动, 只需要一次遍历, 当快指针到终点, 慢指针对应位置, 做删除节点操作.
代码:
- # Definition for singly-linked list.
- # class ListNode:
- # def __init__(self, x):
- # self.val = x
- # self.next = None
- class Solution:
- def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
- result = ListNode(0)
- result.next,fast,slow = head,result,result
- for i in range(n):
- fast = fast.next
- while fast:
- fast = fast.next
- slow = slow.next if fast else slow
- slow.next = slow.next.next
- return result.next
来源: http://www.bubuko.com/infodetail-3529887.html