大家好,我是程序员吴师兄,欢迎来到图解 LeetCode 专栏,在这个专栏我将使用图片和动画帮助你更好的思考。

AlgoMooc 算法慕课网,每道题目都有动画和图片,致力于帮助每个程序员通过算法面试!

今天分享的题目来源于 LeetCode 上第 19 号问题:删除链表的倒数第 N 个节点

一、题目描述

给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。

示例:

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后,链表变为 1->2->3->5.

说明:

给定的 n 保证是有效的。

进阶:

你能尝试使用一趟扫描实现吗?

二、题目解析

直接来思考如何通过 一次遍历 来解决问题。

由于只允许一次遍历,所以不能用一次完整的遍历来统计链表中元素的个数,而是遍历到对应位置就应该移除了。

那么就需要用两个指针来帮助解题,precur 指针。

首先通过一个循环,让 cur 指针 向前走 N 步,如果此时 cur 指向空,说明 N 为链表的长度,则需要移除的为首元素,那么此时返回 head->next 即可。

如果 cur 存在,再继续往下走,此时 pre 指针也跟着走,直到 cur 为最后一个元素时停止,此时 pre 指向要移除元素的前一个元素,再修改指针跳过需要移除的元素即可。

三、动画描述

四、图片描述

LeetCode 第 19 号问题:删除链表的倒数第 N 个节点.002

LeetCode 第 19 号问题:删除链表的倒数第 N 个节点.003

LeetCode 第 19 号问题:删除链表的倒数第 N 个节点.004

LeetCode 第 19 号问题:删除链表的倒数第 N 个节点.005

LeetCode 第 19 号问题:删除链表的倒数第 N 个节点.006

LeetCode 第 19 号问题:删除链表的倒数第 N 个节点.007

LeetCode 第 19 号问题:删除链表的倒数第 N 个节点.008

LeetCode 第 19 号问题:删除链表的倒数第 N 个节点.009

LeetCode 第 19 号问题:删除链表的倒数第 N 个节点.010

LeetCode 第 19 号问题:删除链表的倒数第 N 个节点.011

LeetCode 第 19 号问题:删除链表的倒数第 N 个节点.012

LeetCode 第 19 号问题:删除链表的倒数第 N 个节点.013

五、参考代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //构建虚拟节点
        ListNode dummy = new ListNode(0);
        // 虚拟节点指向原链表的头部
        dummy.next = head;
        // 构建两个指针,都指向虚拟节点 dummy
        ListNode pre = dummy, cur = dummy;
        // 通过一个循环,让 cur 指针 先 向前走 n 步
        for (; n > 0 && pre.next != null; --n) cur = cur.next;
        // 删除的是链表头部节点
        if (n != 0) return head.next;
        // cur 存在,两个指针一直向前移动
        while (cur.next != null) {
             pre = pre.next;
             cur = cur.next;
        }
        // 通过修改指针的位置,删除了需要修改的节点
        pre.next = pre.next.next;
        return dummy.next;

    }
}

六、复杂度分析

时间复杂度

时间复杂度为 O(k)。

空间复杂度

空间复杂度为 O(1)。

七、相关标签

  • 链表
  • 双指针

发表评论

邮箱地址不会被公开。 必填项已用*标注

评论(1)

  • 摸摸头 会员 2021年7月22日 下午2:24

    这句 if (n != 0) return head.next; 判断是否是头部节点,是不是可以删掉?这句话我感觉没什么用处吧。