LeetCode 19. 删除链表的倒数第 N 个结点
题目描述
思路分析
快慢指针问题
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func removeNthFromEnd(head *ListNode, n int) *ListNode {
dummy := &ListNode{Next: head}
slow, fast := dummy, dummy
for i := 0; i <= n; i++ {
fast = fast.Next
}
for fast != nil {
slow = slow.Next
fast = fast.Next
}
slow.Next = slow.Next.Next
return dummy.Next
}
时间复杂度：$O(L)$。我们只对链表进行了一次完整的遍历。
空间复杂度：$O(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
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
// 1. 创建哨兵结点，简化删除头结点的逻辑
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode fast = dummy;
ListNode slow = dummy;
// 2. 快指针先走 n + 1 步
// 走 n + 1 步是为了让 slow 最终停在待删除结点的前一个位置
for (int i = 0; i <= n; i++) {
fast = fast.next;
}
// 3. 快慢指针同时移动，直到快指针到达链表末尾
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
// 4. 此时 slow 指向待删除结点的前驱，执行删除
slow.next = slow.next.next;
// 5. 返回真正的头结点
return dummy.next;
}
}
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！