算法刷题_删除链表的倒数第N个结点

算法刷题Day8_删除链表的倒数第N个结点

文章目录

• 算法刷题Day8_删除链表的倒数第N个结点
• 前言
• 一、双指针思想
• 二、具体步骤
• • 1.定义快慢指针
  • 2.fast指针先移动n+1步
  • 3.fast和slow一起移动
  • 4.删除倒数第N个节点
• 三、完整代码
• 总结

前言

一、双指针思想

双指针的经典应用，如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。

二、具体步骤

1.定义快慢指针

代码如下（示例）：

ListNode *dummyhead=new ListNode(0);
dummyhead->next=head;
ListNode *fast=dummyhead;
ListNode *slow=dummyhead;

2.fast指针先移动n+1步

fast 指针先提前向前移动 n+1 步；
然后 slow 和 fast 同时移动，直到 fast 到达链表末尾。
此时，slow 指针正好指向 待删除节点的前一个节点。为了确保 slow 指针最终指向待删除节点的前一个节点，我们需要让 fast 和 slow 在后续同时移动时，保持一定的间距(n+1)。假如我们不让 fast 再多走一步（即不执行 fast = fast->next;），当 fast 到达最后一个节点时，slow 会停在 待删除节点的位置，

代码如下（示例）：

while(n--&&head!=NuLL){
	fast=fast->next;
	}
fast=fast->next;//fast再提前走一步，因为需要让slow指向删除节点的上一个节点;

3.fast和slow一起移动

代码如下（示例）：

while(fast!=NuLL){
	fast=fast->next;
	slow=slow->next;
	}

4.删除倒数第N个节点

代码如下（示例）：

slow->next=slow->next->next;

三、完整代码

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyhead=new ListNode(0);
        dummyhead->next=head;
        ListNode* fast=dummyhead;
        ListNode* slow=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+1
目的： 确保 slow 指向待删除节点的前一个节点，从而方便删除操作。
如何实现： 通过让 fast 在初始化阶段多走一步，建立 n+1 的间距，然后 fast 和 slow 再同时移动直到 fast 到达链表末尾。