开发者LT的博客
0%

力扣021-删除链表的倒数第n个节点-题解

发表于 分类于
本文字数： 1.5k 阅读时长 ≈ 1 分钟
双指针思想

题目描述

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

示例

示例 1：

img

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

示例 2：

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

示例 3：

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

说明/提示

提示：

  • 链表中结点的数目为 sz
  • 1 <= sz <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz

接口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        
    }
};

思路

破解本题的关键在于怎么仅通过一次遍历就能找到单链表中倒数第n个节点的前置节点。

这里用到了一个很巧妙的数学思想：定义两个指针p和q，p指向第一个节点，q指向头节点（如果没有头节点则自己创建）。p先向后遍历n-1次，这样就找到了正数第n个节点。然后p和q同时向后遍历，直到q为nullptr。假设总共有k个节点，则此时p和q各自向后遍历了k-n+1次，q此时就指向了正数第k-（k-n+1）=n-1个节点上，也就是要删除的前置节点。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        //创建头节点
        ListNode Head;
        Head.next=head;
        //创建两个指针
        ListNode* q=&Head;
        ListNode* p=head;
        for(int i=0;i<n;i++)
        {
            p=p->next;
        }
        while(p!=nullptr)
        {
            p=p->next;
            q=q->next;
        }
        //保存前置节点
        ListNode* pre=q;
        q=q->next;
        //连接前后节点
        pre->next=q->next;
        //删除节点
        delete q;
        //返回第一个节点（题目中所谓的“头节点0
        //注意这里不能返回head，因为有可能会出现删除的就是第一个节点的情况，此时head指向的内存已经被释放
        return Head.next;
    }
};