![](/style/images/good.png)
![](/style/images/bad.png)
LeetCode 图解 | 19.删除链表的倒数第N个节点
source link: https://www.cxyxiaowu.com/8327.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
点击上方蓝字设为星标
今天分享的题目来源于 LeetCode 上第 19 号问题:删除链表的倒数第N个节点。
给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
示例:
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后,链表变为 1->2->3->5.
说明:
给定的 n 保证是有效的。
进阶:
你能尝试使用一趟扫描实现吗?
直接来思考如何通过 一次遍历 来解决问题。
由于只允许一次遍历,所以不能用一次完整的遍历来统计链表中元素的个数,而是遍历到对应位置就应该移除了。
那么就需要用两个指针来帮助解题,pre
和 cur
指针。
首先通过一个循环,让 cur
指针 先 向前走 N 步,如果此时 cur
指向空,说明 N
为链表的长度,则需要移除的为首元素,那么此时返回 head->next 即可。
如果 cur
存在,再继续往下走,此时 pre
指针也跟着走,直到 cur
为最后一个元素时停止,此时 pre
指向要移除元素的前一个元素,再修改指针跳过需要移除的元素即可。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy, cur = dummy;
for (; n > 0 && pre.next != null; --n) cur = cur.next;
if (n != 0) return dummy.next;
while (cur.next != null) {
pre = pre.next;
cur = cur.next;
}
pre.next = pre.next.next;
return dummy.next;
}
}
复杂度分析
-
时间复杂度:O(k)。
-
空间复杂度:O(1)。
相关题目推荐
-
LeetCode 26:删除排序数组中的重复项
-
LeetCode 203:移除链表元素
![LeetCode 图解 | 19.删除链表的倒数第N个节点](https://cxyxiaowu-1257126549.cos.ap-guangzhou.myqcloud.com/2020/02/1581434233-54a758c20d5a81c.jpeg)
原文始发于微信公众号(图解面试算法):LeetCode 图解 | 19.删除链表的倒数第N个节点
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK