[19] Remove Nth Node From End of List 删除链表的倒数第N个节点

[19] Remove Nth Node From End of List

力扣题目链接

1. 快慢指针

1.1 思想

使用快慢指针一趟扫描，找到待删除节点的前驱节点。

• 创建两个指针 fast 和 slow，都初始化为dummyHead。
• 建立距离: 让 fast 指针先向前移动 n 步。此时，fast 和 slow 之间就形成了一个固定的、长度为 n 的“窗口”。
• 同步前进: 然后，同时移动 fast 和 slow 指针，一步一步向后，直到 fast 指针到达链表的最后一个节点(fast->next == nullptr)。
• 精准定位: 在同步前进的过程中，因为 fast 和 slow 之间始终保持着 n 个步长的距离，所以当 fast 到达链表末尾时，slow 指针恰好位于倒数第 n 个节点的前一个节点。
• 快慢指针之间的距离为n个步长，当快指针为倒数第一个节点时，他与最后一个节点的距离为0，此时慢指针与最后一个节点的距离为n，所以慢指针指向的是倒数n+1个节点。

1.2 AC代码

ListNode *removeNthFromEnd(ListNode *head, int n) { // 创建虚拟头节点，统一操作 ListNode *dummyHead = new ListNode(0); dummyHead->next = head; ListNode *f = dummyHead; ListNode *s = dummyHead; // 快指针先向前移动 n 步 while (n-- && f != nullptr) { f = f->next; } // 快慢指针同步前进，直到 fast 到达最后一个节点 // 此时 slow 正好在待删除节点的前一个位置 while (f->next != nullptr) { f = f->next; s = s->next; } // 删除操作 ListNode *toDelete = s->next; s->next = toDelete->next; delete toDelete; // 释放内存 // 返回新链表的头节点 ListNode *realHead = dummyHead->next; delete dummyHead; return realHead; }

1.3 时空复杂度

时间复杂度: O(N)。其中 N 是链表的长度。快指针总共遍历了整个链表一次。

空间复杂度: O(1)。只使用了 fast, slow 等常数个额外指针变量。