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

​
​

作者简介：C/C++ 、Golang 领域耕耘者，创作者
个人主页：作者主页
活动地址：CSDN21天学习挑战赛
题目来源： leetcode官网
如果感觉博主的文章还不错的话，还请关注➕ 、点赞👍 、收藏🧡三连支持一下博主哦~~~

💜 题目描述

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

示例1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例2：

输入：head = [1], n = 1
输出：[]

示例3：

输入：head = [1,2], n = 1
输出：[1]

🧡 算法分析

此题方法是用遍历法

算法步骤:

1. 因为链表头节点可能被遍历删除，所有这里需要创建一个虚拟节点指向链表头节点
2. 遍历整个链表， 计算链表长度，加上虚拟节点（后面在计算位置记得加上 虚拟节点即可）
3. 找到倒数第n个节点的前一个节点，修改此节点的next指针即可

方法二： 双指针
4. left 指针在前面走， right 指针在后面
5. 刚开始right 先走n步， 然后两个指针同时走， 直到right指针走到最后，这时left指针指向倒数第n个节点前一个
6. 修改节点next 指针即可

💚 代码实现

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // head 需要遍历，可能被删除，这里new 一个虚拟节点
        auto dummy = new ListNode(-1);
        dummy->next = head;
        int k = 0;
        for(auto p = dummy; p ; p = p->next) k ++;

        cout << k << endl;

        auto p = dummy;
        for(int i = 0; i < k - n - 1; i ++) p = p->next;
        p->next = p->next->next;
        cout << p->val << ' ';

        return dummy->next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

方法二：

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // head 需要遍历，可能被删除，这里new 一个虚拟节点
        auto dummy = new ListNode(-1);
        dummy->next = head;
        auto r = dummy, l = dummy;
        for(int i = 0 ;i <= n; i ++) r = r->next;
        for( ; r; r = r->next) l = l->next;

        l->next = l->next->next;

        return dummy->next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

执行结果：

💙 时间复杂度分析

其中遍历一次， 时间复杂度为O(n)

如果觉得对你有帮助的话:
👍 点赞，你的认可是我创作的动力！
🧡 收藏，你的青睐是我努力的方向！
✏️ 评论，你的意见是我进步的财富！