原题地址:. - 力扣(LeetCode)
给你一个链表,删除链表的倒数第 n
个结点,并且返回链表的头结点。
示例 1:
输入:head = [1,2,3,4,5], n = 2 输出:[1,2,3,5]
示例 2:
输入:head = [1], n = 1 输出:[]
解析
在链表中删除某个节点,其实就是将之前一个节点next,直接指向当前节点的后一个节点,相当于“跳过”了这个节点。
计算链表长度(二次遍历)
最简单的想法是,我们首先从头节点开始对链表进行一次遍历,得到链表的长度 L。
然后,我们再从头节点开始对链表进行一次遍历,当遍历到第 L-N+1 个节点时,它就是我们需要删除的倒数第N个节点。
这样,总共做两次遍历,我们就可以得到结果。
public ListNode removeNthFromEnd(ListNode head, int n) {
int length = 0;
ListNode cur = head;
while (cur != null) {
length++;
cur = cur.next;
}
ListNode sentinel = new ListNode(-1, head);
cur = sentinel;
for (int i = 0; i < length - n; i++) {
cur = cur.next;
}
cur.next = cur.next.next;
return sentinel.next;
}
双指针
我们可以使用两个指针 first 和 second 同时对链表进行遍历,要求 first 比 second 超前 N 个节点。
这样,它们总是保持着N的距离,当 first 遍历到链表的末尾(null)时,second 就恰好处于第L-N+1,也就是倒数第 N 个节点了。
public ListNode removeNthFromEnd1(ListNode head, int n) {
ListNode sentinel = new ListNode(-1, head);
ListNode first = sentinel;
ListNode second = head;
for (int i = 0; i < n; i++) {
second = second.next;
}
while (second != null) {
first = first.next;
second = second.next;
}
first.next = first.next.next;
return sentinel.next;
}