目录
题目链接:LCR 021. 删除链表的倒数第 N 个结点 - 力扣(LeetCode)
题目:
如果给定一个链表,请问如何删除链表中的倒数第 n 个节点?假设链表中节点的总数为 sz,那么 1 <= n <= sz。要求只能遍历链表一次。
例如,输入下图 (a) 中的链表,删除倒数第 2 个节点之后的链表如下图 (b) 所示。
如果可以遍历链表两次,那么这个问题就会变得简单一些。在第 1 次遍历链表时,可以得出链表的节点总数 sz。在第 2 次遍历链表时,可以找出链表的第 sz - n 个节点(即倒数第 n + 1 个节点)。然后把倒数第 n + 1 个节点的 next 指针指向倒数第 n - 1 个节点,这样就可以把倒数第 n 个节点从链表中删除。
class Solution {
public:
? ?ListNode* removeNthFromEnd(ListNode* head, int n) {
? ? ? ?int sz = 0;
? ? ? ?ListNode* cur = head;
? ? ? ?while (cur)
? ? ? {
? ? ? ? ? ?++sz;
? ? ? ? ? ?cur = cur->next;
? ? ? }
? ? ? ?ListNode* prev = nullptr;
? ? ? ?for (int i = 0; i < sz - n; ++i)
? ? ? {
? ? ? ? ? ?if (i == 0)
? ? ? ? ? ? ? ?prev = head;
? ? ? ? ? ?else
? ? ? ? ? ? ? ?prev = prev->next;
? ? ? }
?
? ? ? ?ListNode* del;
? ? ? ?if (prev == nullptr)
? ? ? {
? ? ? ? ? ?del = head;
? ? ? ? ? ?head = head->next;
? ? ? }
? ? ? ?else
? ? ? {
? ? ? ? ? ?del = prev->next;
? ? ? ? ? ?prev->next = prev->next->next;
? ? ? }
? ? ? ?delete del;
? ? ? ?return head;
? }
};
注意:如果 n 等于链表的节点总数 sz,那么被删除的节点为原始链表的头节点。
但题目要求只能遍历链表一次。为了实现只遍历链表一次就能找到倒数第 n + 1 个节点,可以定义两个指针。第 1 个指针 P1 从链表的头节点开始向前走 n 步,第 2 个指针 P2 保持不动;从第 n + 1 步开始指针 P2 也从链表的头节点开始和指针 P1 以相同的速度遍历。由于两个指针的距离始终保持 n,当指针 P1 指向链表的尾节点时指针 P2 正好指向倒数第 n + 1 个节点。
下面以在有 6 个节点的链表中找倒数第 3 个节点为例一步步分析这个过程。首先用第 1 个指针 P1 从头节点开始向后走 2 步到达第 3 个节点,如下图 (a) 所示。然后初始化第 2 个指针 P2,让它指向链表的头节点,如下图 (b) 所示。最后让两个指针同时向后遍历,当指针 P1 到达链表的为尾节点时指针 P2 刚好指向倒数第 3 个节点,如下图 (c) 所示。
找出链表中倒数第 3 个节点之后再删除倒数第 2 个节点就比较容易,只需要把倒数第 3 个节点的 next 指针指向倒数第 1 个节点就可以。
class Solution {
public:
? ?ListNode* removeNthFromEnd(ListNode* head, int n) {
? ? ? ?ListNode* front = head;
? ? ? ?for (int i = 0; i < n; ++i)
? ? ? {
? ? ? ? ? ?front = front->next;
? ? ? }
?
? ? ? ?if (front == nullptr)
? ? ? {
? ? ? ? ? ?ListNode* del = head;
? ? ? ? ? ?head = head->next;
? ? ? ? ? ?return head;
? ? ? }
?
? ? ? ?ListNode* back = head;
? ? ? ?while (front->next)
? ? ? {
? ? ? ? ? ?front = front->next;
? ? ? ? ? ?back = back->next;
? ? ? }
? ? ? ?ListNode* del = back->next;
? ? ? ?back->next = back->next->next;
? ? ? ?delete del;
? ? ? ?return head;
? }
};