leetcode.Q19.删除链表的倒数第N个节点

解析思路

leetcode 中等难度,题目描述点击这里

第一眼看过去很多人都能想到两次编辑即可。第一次遍历获取链表长度,第二次遍历走到对应位置即可。

但是题目进阶描述中要求用一次遍历来实现。

通常涉及到链表位置问题的我们都可以考虑用快慢指针来实现。题目删除倒数第n个节点,那么我们可以:

  • 定义pq两个指针
  • 先让q走n步,等到q走到最后一个节点时,p刚好在倒数第n-1个节点上,删除p的下一个节点即可
  • 考虑特殊情况,n等于链表长度,这种情况下当q走n步时,刚好为null,为null时直接返回p的下一个节点即可,返回p.next
  • 让q走到最后一个节点,再删除p的下一个节点
  • 返回head

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode p = head, q = head;
//先将p,q的距离差拉到n,这样当q在结尾时,刚好p在倒数第n+1个位置上,删除下一个位置即可
while ((n--) > 0) {
q = q.next;
}
//考虑特殊情况,当n等于链表长度时,需要删除第一个元素
if (q == null) {
return p.next;
}
//让q走到结尾
while (q.next != null) {
q = q.next;
p = p.next;
}
//删除p的下一个节点
p.next = p.next.next;
return head;
}
本文原创发布于:https://blog.fleyx.com,转载请注明出处

如果本篇文章对您有帮助欢迎打赏哦!
微信打赏 支付宝打赏
关注公众号(烦嚣的人)
微信公众号