乐趣区

[LeetCode]删除链表的倒数第N个节点(Remove Nth Node From End of List)

题目描述
给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
示例:
给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后,链表变为 1->2->3->5. 说明:给定的 n 保证是有效的。
进阶:你能尝试使用一趟扫描实现吗
ListNode 数据结构
class ListNode {
int val;
ListNode next;

ListNode(int x) {
val = x;
}
}
解决方法
如何一趟遍历获取倒数第 n 个节点?使用 2 个指针 first,second,first 在前,second 在后,保持间隔 n 走到链尾,这样 second 就是倒数第 n 个节点
如何删除当前节点操作?前一个节点.next = 前一个节点.next.next
由于头节点没有前一个节点了,如何删除头节点?在头节点前面加入临时头节点,这样原头节点就和普通节点一致
解决了上述 3 个问题可得出以下代码
public ListNode removeNthFromEnd(ListNode head, int n) {
// 为了方便操作建立临时头节点
ListNode tempHead = new ListNode(0);
tempHead.next = head;
ListNode first = tempHead;
ListNode second = tempHead;
// 让 first 先走 n + 1 步
for (int i = 1; i <= n + 1; i++) {
first = first.next;
}
// 两个指针一起走,当 first 走到链尾,second 就走到倒数第 n + 1 个节点
while (first != null) {
first = first.next;
second = second.next;
}
// 删除下一个节点即删除倒数第 n 个节点
second.next = second.next.next;
return tempHead.next;
}
本文首发:https://lierabbit.cn/2018/08/…

退出移动版