1 题目描述
19. 删除链表的倒数第 N 个结点要求给定一个链表,任务是删除链表的倒数第 n
个结点,并且返回链表的头结点。
2 解题思路
本题可以通过双指针的方法来解决。具体来说,可以使用两个指针 slow
和 fast
,它们都初始化在哑节点 dummy
上。fast
指针先向前移动 n + 1
步,然后两个指针同时移动,直到 fast
指针到达链表的末尾。这时,slow
指针恰好位于要删除节点的前一个位置。删除该节点后,返回哑节点的 next
指针即可。
3 Java 代码实现
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head); // 创建一个哑节点作为头结点
ListNode fast = dummy, slow = dummy;
// 让 fast 指针先走 n+1 步
for (int i = 0; i <= n; i++) {
fast = fast.next;
}
// 同时移动 fast 和 slow 指针,直到 fast 到达链表末尾
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
// 删除目标节点
slow.next = slow.next.next;
return dummy.next;
}
}
- 时间复杂度: O(L),其中 L 是链表的长度。每个节点只遍历一次。
- 空间复杂度: O(1),只用了常量级别的额外空间。
4 注意事项
- 哑节点:引入哑节点
dummy
以简化代码逻辑,避免处理头节点的特殊情况。 - 双指针:使用两个指针
slow
和fast
,fast
指针先前进n + 1
步,确保当fast
指针到达链表末尾时,slow
指针位于要删除节点的前一个位置。 - 删除节点:当
fast
指针到达链表末尾时,slow
指针指向要删除节点的前一个位置,通过slow.next = slow.next.next
完成删除操作。 - 返回新头节点:返回
dummy.next
作为新的链表头节点。