LeetCode 图解 | 19.删除链表的倒数第N个节点

点击上方蓝字设为星标LeetCode 图解 |  19.删除链表的倒数第N个节点

下面开始今天的学习~

LeetCode 图解 |  19.删除链表的倒数第N个节点


今天分享的题目来源于 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 != 0return 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个节点

LeetCode 图解 |  19.删除链表的倒数第N个节点

原文始发于微信公众号(图解面试算法):LeetCode 图解 | 19.删除链表的倒数第N个节点

本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » LeetCode 图解 | 19.删除链表的倒数第N个节点

我还会在以下平台发布内容

GitHub 哔哩哔哩