19. 删除链表的倒数第 N 个结点
小于 1 分钟
19. 删除链表的倒数第 N 个结点
题目:
给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。
leetcode地址:https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
solution
class Solution {
// 主函数
public ListNode removeNthFromEnd(ListNode head, int n) {
// 虚拟头结点
ListNode dummy = new ListNode(-1);
dummy.next = head;
// 删除倒数第 n 个,要先找倒数第 n + 1 个节点
ListNode x = findFromEnd(dummy, n + 1);
// 删掉倒数第 n 个节点
x.next = x.next.next;
return dummy.next;
}
// 返回链表的倒数第 k 个节点
ListNode findFromEnd(ListNode head, int k) {
ListNode p1 = head;
// p1 先走 k 步
for (int i = 0; i < k; i++) {
p1 = p1.next;
}
ListNode p2 = head;
// p1 和 p2 同时走 n - k 步
while (p1 != null) {
p2 = p2.next;
p1 = p1.next;
}
// p2 现在指向第 n - k 个节点
return p2;
}
}
// 详细解析参见:
// https://labuladong.github.io/article/?qno=19
版权申明
本站点所有内容,版权均归https://wenchao.ren所有,除非明确授权,否则禁止一切形式的转载协议
打赏
