从列表LeetCode的末尾删除第N个节点

Question

我正在进行从列表末尾删除第N个节点LeetCode挑战：

给定链表的head，从列表末尾移除第^个节点的n^{并返回其头。}

跟进：你能一次性完成吗？

我的代码在一些测试用例中失败：

[1,2]
2

我得到了这个报告：

Output [1]
Expected [2]

我已经阅读了解决方案，似乎我的解决方案与编写的解决方案相同，但我不知道我的错误在哪里。我的代码如下：

def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
pointer1 = head
pointer2 = head
count = 0
if not pointer1.next:
return pointer1.next
while pointer2 is not None:
if count > n:
pointer1 = pointer1.next
pointer2 = pointer2.next
count += 1
pointer1.next = pointer1.next.next
return head

我已经做了半个小时了，我不知道该怎么修。有人能帮忙吗？

Answer 1

当n等于列表中的节点数时，您的解决方案将失败。在这种情况下，您应该从列表中删除第一个节点，因此您应该返回head.next。

注意：while循环之前的if测试该情况的一个非常特定的实例，即当列表只有一个元素时。但如上所述，此操作应适用于比if中确定的更通用的情况。

因此，可以放弃以下if条件：

if not pointer1.next:
return pointer1.next

并在while循环后添加一个条件：

def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
pointer1 = head
pointer2 = head
count = 0
while pointer2 is not None:
if count > n:
pointer1 = pointer1.next
pointer2 = pointer2.next
count += 1
if count > n:
pointer1.next = pointer1.next.next
return head  
else:
return head.next

Answer 2

只是在Java代码片段中共享方法(以防有人对此问题感兴趣(

方法#1

使用两次迭代-在第一次迭代中找到列表中元素的总数，以找到要从数组开头删除的元素的索引并将其删除。

public ListNode removeNthFromEnd(ListNode head, int n) {
if (head == null) {
return null;
}
if (n < 0) {
return head;
}
//find size of the list
int size = 0;
ListNode current = head;
while (current != null) {
size++;
current = current.next;
}
if (n > size) {
return head;
}
int indexOfTheElementToDelete = size - n;
ListNode previous = null;
current = head;
int currentNodeIndex = 0;
while (currentNodeIndex < indexOfTheElementToDelete) {
previous = current;
current = current.next;
currentNodeIndex++;
}
if (previous != null) {
if (current != null) {
previous.next = current.next;
current.next = null;
} else {
// last element to delete
previous.next = null;
}
return head;
}
// first element
ListNode newHead = current.next;
current.next = null;
return newHead;
}

方法#2

1. 它只遍历列表一次

2. 为了实现这一点，基本思想是保持两个总是相距n的指针(比如慢指针和快指针(。移动它们，使快速指针到达末尾——下面的代码片段提供了详细信息。

   public ListNode removeNthFromEnd(ListNode head, int n) {
   if (head == null) {
   return null;
   }
   if (n <= 0) {
   return head;
   }
   ListNode start = new ListNode();
   start.next = head;
   ListNode slow = start;
   ListNode fast = head;
   int indexOfFastNode = 1;
   while (indexOfFastNode < n && fast.next != null) {
   fast = fast.next;
   indexOfFastNode++;
   }
   if (n > indexOfFastNode) {
   return head;
   }
   while (fast.next != null) {
   fast = fast.next;
   slow = slow.next;
   }
   ListNode temp = slow.next;
   slow.next = slow.next.next;
   temp.next = null;
   return start.next;
   }