LeetCode 19. 删除链表的倒数第 N 个结点
题目描述
思路分析
我们可以使用双指针的方法来解决这个问题。具体步骤如下：
- 初始化两个指针：
first和second，都指向链表的头节点。- 移动第一个指针：让
first指针先移动 N 步，这样first和second之间的距离为 N。- 同时移动两个指针：当
first指针到达链表的末尾时，second指针正好指向要删除的节点的前一个节点。- 删除节点：修改
second指针的next指向second.next.next，从而删除倒数第 N 个节点。- 返回头节点：如果删除的是头节点，返回新的头节点。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
func removeNthFromEnd(head *ListNode, n int) *ListNode {
dummy := &ListNode{Next: head}
first, second := dummy, dummy
for i := 0; i < n; i++ {
first = first.Next
}
for first != nil && first.Next != nil {
first = first.Next
second = second.Next
}
second.Next = second.Next.Next
return dummy.Next
}
1
2
3
4
5
6
7
8
9
10
11
12
13
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 && fast.Next != nil {
fast = fast.Next
slow = slow.Next
}
slow.Next = slow.Next.Next
return dummy.Next
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode();
dummy.next = head;
ListNode slow = dummy, fast = dummy;
for (int i = 0; i < n; i++) {
fast = fast.next;
}
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return dummy.next;
}
}
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！