从列表末尾删除第 n 个位置的节点（Leet 代码问题 19）

Question

我正在尝试解决 LeetCode 挑战 19. Remove Nth Node From End of List:

Given the head of a linked list, remove the n^th node from the end of the list and return its head.

Constraints

The number of nodes in the list is sz.

1 <= sz <= 30

0 <= Node.val <= 100

1 <= n <= sz

下面是我的函数。它使用2指针方法。它适用于许多测试用例，除了这个：

链表=[1,2,3]
n = 3

def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
    if head is None or head.next is None:
        return None
    if head.next.next is None :
        if(n ==1):
            head.next = None
            return head
        if(n == 2):
            head = head.next
            return head 
            
    slow_pointer = head 
    fast_pointer = head
    for i in range(n+1):
        fast_pointer = fast_pointer.next
    while(fast_pointer is not None):
        fast_pointer = fast_pointer.next
        slow_pointer = slow_pointer.next
    slow_pointer.next = slow_pointer.next.next
    return head

我哪里错了？

Answer 1

您的代码没有处理需要删除 head 节点的一般情况。一开始它确实处理了一些这样的情况（当列表的大小小于 3 时），但这显然不会对更大的列表起作用。

问题是，当n是列表的大小时，那么这个循环在最后一次迭代中会出错，因为它会从fast_pointer开始等于None:

for i in range(n+1):
    fast_pointer = fast_pointer.next

因此，您应该单独处理最后一次迭代，而不是作为此循环的一部分。使循环一次迭代更短，并在可能的情况下单独执行最后一个“移动”：

for i in range(n):
    fast_pointer = fast_pointer.next
if fast_pointer is None:
    return head.next  # remove first node
fast_pointer = fast_pointer.next

...然后您的代码的最后部分可以保持原样。

通过此更改，您实际上不必在代码开头处理那么多特殊情况。事实上，（在 LeetCode 上）给出列表将有至少一个节点。所以你实际上没有任何边界情况需要处理。

应用这些更改，您的代码变为：

def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
    slow_pointer = head 
    fast_pointer = head
    for i in range(n):
        fast_pointer = fast_pointer.next
    if fast_pointer is None:
        return head.next  # remove first node
    fast_pointer = fast_pointer.next
    while fast_pointer is not None:
        fast_pointer = fast_pointer.next
        slow_pointer = slow_pointer.next
    slow_pointer.next = slow_pointer.next.next
    return head

Answer 2

class Solution:
    def remove(self,head:ListNode,n:int)->ListNode:
        dummy=ListNode(0,head)
        # pay attention that left starts at dummy
        left=dummy
        right=head
        # this makes sure, right is n step ahead of left
        while n>0 and right:
            right=right.next
            n-=1
        # when right reaches the end, left would be the previous of the node that we delete
        # that is why left started at dummy node
        while right:
            left=left.next
            right=right.next
        # now delete it
        left.next=left.next.next
        return dummy.next

从列表末尾删除第 n 个位置的节点（Leet 代码问题 19）

Delete node at nth position from the end of a list (Leet code problem 19)

python

linked-list

recursive-datastructures

Constraints