Keshawn_lu's Blog

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

字数统计: 310阅读时长: 1 min
2020/10/18 Share

题目简介:

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

示例:

1
2
3
给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后,链表变为 1->2->3->5.

说明:

给定的 n 保证是有效的。

进阶:

你能尝试使用一趟扫描实现吗?

思路:

首先定义一个快指针,让其先走n。然后快慢指针一起走,当quick == NULL时,慢指针所指向的结点便是要删除的结点。

在慢指针走的过程中,保存其前驱结点,用于删除结点。

tip:

  • 注意删除的是第一个结点时的情况特判。

代码如下:

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
/**
* 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* quick = head;
ListNode* slow = head; //待删结点

while(n > 0){

quick = quick -> next;
n--;
}

ListNode* pre = NULL;
while(quick){

pre = slow;
slow = slow -> next;
quick = quick -> next;
}

if(pre == NULL)
return head -> next; //删除的是第一个结点

pre -> next = slow -> next;

return head;
}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: