19.删除链表的倒数第N个结点

发表于： 分类于：
字数： 488 阅读：≈ 1分钟

👋 19.删除链表的倒数第N个结点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

思路

基本思想

为了删除倒数第n个节点，最简单的办法就是求出链表的长度，然后再找到倒数第n个节点的前一个节点进行删除，此时就需要两次遍历，第一次求出链表长度，第二次找到倒数第n个节点的前一个节点，为了简化流程，想到一个更简单的办法

定义两个变量，使用双指针，快指针先走n步，然后快慢指针一起走，当快指针移动到末尾时，慢指针就移动到了倒数第n个节点，为了找到倒数第n个节点的前一个节点，并且当链表中只有一个节点时也能完美删除，申请一个虚拟头结点，让链表的操作变得统一

核心就是双指针+虚拟头结点

执行流程

  1. 申请虚拟头结点，虚拟头结点的next指针指向链表的首元结点
  2. 快慢指针都从虚拟头结点出发
  3. 快指针走n步
  4. 快慢指针一起走，当快指针到了末尾，慢指针就到了倒数第n个节点的前一个节点
  5. 删除节点，返回虚拟头结点的next指针

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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

总结

核心就是快慢指针+虚拟头结点