代码随想录 19.删除链表的倒数第N个节点

删除链表的倒数第N个节点的解法包括直观解法、快慢指针法和栈解法，具体实现如下：

• 直观解法

  思路：先统计链表长度，再根据长度和n的关系找到待删除节点的前驱节点，修改指针完成删除。

  步骤：

  创建虚拟头节点dummyNode简化边界条件处理。

  遍历链表统计节点数count_sum。

  根据count_sum和n的关系移动指针到待删除节点的前驱节点。

  修改指针并释放待删除节点的内存。

  处理特殊情况（如链表只有一个节点且n=1时返回空链表）。

  代码：

  class Solution {public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummyNode = new ListNode(0); dummyNode->next = head; ListNode* currentNode = dummyNode; long long count_sum = 0; while (currentNode->next) { count_sum++; currentNode = currentNode->next; } ListNode* tmpNode = dummyNode; if (count_sum == 1 && n == 1) { delete tmpNode->next; return nullptr; } while (tmpNode->next && tmpNode->next->next) { if (count_sum == n) { ListNode* tmp1 = tmpNode->next; tmpNode->next = tmpNode->next->next; delete tmp1; } else { tmpNode = tmpNode->next; } count_sum--; } if (n == 1) { ListNode* tmp1 = tmpNode->next; tmpNode->next = nullptr; delete tmp1; } return dummyNode->next; }};

• 快慢指针法

  思路：通过快指针先走n+1步，使快慢指针保持n个节点的间隔，当快指针到达末尾时，慢指针指向待删除节点的前驱节点。

  步骤：

  创建虚拟头节点dummyHead。

  初始化快慢指针fast和slow指向dummyHead。

  快指针先移动n+1步（代码中通过n-- && fast != nullptr和fast = fast->next实现）。

  快慢指针同步移动，直到快指针到达末尾。

  修改慢指针的next指针跳过待删除节点。

  代码：

  class Solution {public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummyHead = new ListNode(0); dummyHead->next = head; ListNode* slow = dummyHead; ListNode* fast = dummyHead; while(n-- && fast != nullptr) { fast = fast->next; } fast = fast->next; while (fast != nullptr) { fast = fast->next; slow = slow->next; } slow->next = slow->next->next; return dummyHead->next; }};
  

• 栈解法

  思路：利用栈的先进后出特性，将链表节点依次入栈，弹出n个节点后栈顶即为待删除节点的前驱节点。

  步骤：

  创建栈nodeStack存储链表节点。

  遍历链表将所有节点入栈。

  弹出n个节点（倒数第n个节点被弹出）。

  若栈为空，说明待删除节点是头节点，返回head->next。

  否则栈顶节点的前驱节点修改next指针跳过待删除节点。

  代码：

  class Solution {public: ListNode* removeNthFromEnd(ListNode* head, int n) { stack<ListNode*> nodeStack; ListNode* currentNode = head; while (currentNode) { nodeStack.push(currentNode); currentNode = currentNode->next; } for (int i = 0; i < n; i++) { nodeStack.pop(); } if (nodeStack.empty()) { return head->next; } else { ListNode* prevNode = nodeStack.top(); prevNode->next = prevNode->next->next; return head; } }};

三种方法对比：

• 直观解法：时间复杂度O(L)（L为链表长度），空间复杂度O(1)，但代码逻辑较复杂，需处理多种边界条件。
• 快慢指针法：时间复杂度O(L)，空间复杂度O(1)，代码简洁高效，是推荐解法。
• 栈解法：时间复杂度O(L)，空间复杂度O(L)，利用栈结构简化了指针操作，但额外空间开销较大。