如何删除链表的倒数第N个结点？（双指针法快慢指针）（C++实现）

如何删除链表的倒数第N个结点？（双指针法/快慢指针）（C++实现）

 

目录

题目条件

要求

 题解（双指针法/快慢指针）

运行结果 

改进

 运行结果 

---

题目条件

已给出链表结点结构体的定义

一个链表结点包含 一个数据域、一个指针域

还有三种创建新结点的方法

要求

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

// 链表结点伪代码
// Definition for singly - linked list.
struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

 题解（双指针法/快慢指针）

 1.哨兵结点创建在栈区的版本

ListNode* removeNthFromEnd(ListNode* head, int n)
{
    // 双指针法（快慢指针）
    ListNode preHead = ListNode(0, head);  // 哨兵结点->便于引用链表
    ListNode* first = head;  // 前指针从头结点出发
    ListNode* second = &preHead;  // 后指针从哨兵结点出发
    for (; n > 0; n--)  // 前指针先往后挪 N 个结点
    {
        first = first->next;
    }
    while (first)  // 再一起挪，结束时 后指针指向待删除结点的前继结点
    {
        first = first->next;
        second = second->next;
    }

    ListNode* temp = second->next;
    second->next = second->next->next;
    delete temp;

    return preHead.next;  // 不能直接返回head（链表为空时，head指向无效地址）
}

运行结果 

 

改进

栈区版本（速度慢，空间占用还更大？！） 

改进 -> 2.堆区版本

ListNode* removeNthFromEnd(ListNode* head, int n) {
    // 双指针法（快慢指针）
    ListNode* preHead = new ListNode(0, head);  // 哨兵结点->便于引用链表
    ListNode* first = head;  // 前指针从头结点出发
    ListNode* second = preHead;  // 后指针从哨兵结点出发
    for (; n > 0; n--)  // 前指针先往后挪 N 个结点
    {
        first = first->next;
    }
    while (first)  // 再一起挪，结束时 后指针指向待删除结点的前继结点
    {
        first = first->next;
        second = second->next;
    }

    ListNode* temp = second->next;
    second->next = second->next->next;
    delete temp;

    return preHead->next;  // 不能直接返回head（链表为空时，head指向无效地址）
}

 运行结果 

 

 运行速度直接起飞了好吧！