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

链接: https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

题面

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

解法

利用快慢指针,先将fast指针向前移动n个结点,再快慢指针同时移动
当快指针到达链表尾时,慢指针刚好指向倒数第n个结点
利用dummy指针可以规避删除第一个结点的情况

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {

ListNode* dummy = new ListNode(0, head);
ListNode* slow = dummy, *fast = dummy;
for (int i = 0; i < n; i++) {
fast = fast -> next;
}
while(fast != nullptr) {
fast = fast -> next;
if (fast == nullptr) {
slow -> next = slow -> next -> next;
break;
}
else {
slow = slow -> next;
}
}
return dummy -> next;
}
};