删除链表的倒数第N个节点
给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
示例:
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后,链表变为 1->2->3->5.
说明:
给定的 n 保证是有效的。
进阶:
你能尝试使用一趟扫描实现吗?
这个题可以使用双指针,bef
和 aft
,让 bef
先于 aft
指针 n 个元素,如果此时bef
指针指向了null
,即说明指向了末尾即n==链表长度,所以删除的是链表的头节点,此时直接返回head.next
.
另一种情况,两个指针同时移动,当 bef
指针移向尾节点时, aft
指针刚好移动的要删除节点的前一个节点.
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode bef = head;
ListNode aft = head;
for (int i = 0; i < n; i++) {
bef = bef.next;
}
//链表的长度刚好是n,即删除头节点
if (bef==null){
return head.next;
}
while (bef.next!=null){
bef = bef.next;
aft = aft.next;
}
aft.next = aft.next.next;
return head;
}
}