题目
给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
示例:
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后,链表变为 1->2->3->5.
说明:
给定的 n 保证是有效的。
进阶:
你能尝试使用一趟扫描实现吗?
链接:https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
分析及反思
双指针 第一个指针先移动n次,随后第二个指针和第一个指针同步后移 直到第一个的next为null的时候 第二个指针的下一个就是倒数第n个 还是很妙的 这种解法。一次遍历即可完成。
然后就是问题实践解决中,我直接从head开始遍历 没有设置头结点,导致在{[1],1}这个测试点的时候无法删除第一个节点报错的问题。
所以类似的节点问题一定要添加头结点,,是最稳的解法。
代码
//class ListNode {
// int val;
// ListNode next;
//
// ListNode(int x) {
// val = x;
// }
//}
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode pre = new ListNode(0);
pre.next = head;//头节点
ListNode start = pre, end = pre;
while (n-- != 0) {
start = start.next;
}
while (start.next != null) {
start = start.next;
end = end.next;
}
end.next = end.next.next;
return pre.next;
// ListNode p, q;
// p = q = head;
// int count = 0;
// while (q.next != null) {
// if (count != n) {
// q = q.next;
// count++;
// } else {
// q = q.next;
// p = p.next;
// }
// }
// p.next = p.next.next;
// return head;
}
}
本文作者:Author: 寒光博客
文章标题:[LeetCode]19. 删除链表的倒数第N个节点
本文地址:https://dxoca.cn/Algorithm/368.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
本文地址:https://dxoca.cn/Algorithm/368.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。