动图:删除链表的倒数第 N 个结点

举报
程序员小熊 发表于 2021/04/14 16:52:09 2021/04/14
【摘要】 本文采用“双指针 + 动图”的方式,深度剖析“删除链表的倒数第 N 个结点”,步骤清晰,简洁明了!


本文主要介绍一道面试中常考链表删除相关的题目,即 leetcode 19. 删除链表的倒数第 N 个结点。采用 双指针 + 动图 的方式进行剖析,供大家参考,希望对大家有所帮助。

更多精彩文章,请关注公众号【程序员小熊】。

19. 删除链表的倒数第 N 个结点

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

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

解题思路

在链表中要删除某个节点 nodeB,必须先找到 该节点的前一节点 nodeA ,再将 nodeA 指向 nodeB 的下一节点 nodeC ,从而实现节点 nodeB 的删除。

例如要删除链表 L(1->2->3->4->5) 中 值为 3 的节点,首先得找到该节点的前一节点(值为 2 的节点),才能实现该节点的删除,如下图示:

题目要求删除 倒数第 n 个 节点,所以首先得找到 该节点的前一节点 ,但由于不知道 整个链表的长度,因此不知道 待删除的节点是正数的第几个节点,所以很难从头节点开始遍历时删除掉这个节点。

思路一

先遍历一遍链表,获取整个链表的长度;假设整个链表的长度为 l,则可知要删除的节点为第 l - n + 1 个节点;再遍历一遍,删除倒数第 n 个节点。例如链表 L 为 1->2->3->4->5,n = 3,则要删除的节点为 第 5 - 3 + 1 = 3 个节点

思路二

尽管思路一可行,但是需要 遍历链表两遍,不够简洁,而且题目的 进阶 中也提到尝试使用一趟扫描实现,因此本文采用 双指针 的策略,实现通过一次扫描删除 倒数第 n 个节点

在上一期链表相关专题 虚拟头节点秒杀链表问题 中提到 增加虚拟头节点 的策略解决链表问题,增加虚拟头节点的 好处 在于:不需要单独考虑头节点,这样对头节点的处理就像跟其它节点一样。本文也同样采用这种策略。

举栗

以链表 1->2->3->4->5,n = 3 为栗,如下如示。

按照上面分析,先要找到 倒数第 3 个节点的前一节点,即值为 2 的节点

增加虚拟头节点

值为 2 的节点是 倒数第 4 个节点(后往前数),增加两指针 fast/slow,分别指向最后一个元素(NULL)和上图中 target 的位置;

此时 fast 跟 slow 之间的间距是固定(n = 3)的,找到 target(slow)后,只需要删除其下一节点即可,但 slow 指向的节点前面有多少个节点该如何确定呢?

由于当前已知 fast 和 slow 指向节点之间的长度是固定的,只需要将这两个指针向前挪,直到 slow 挪到虚拟头节点(值为 0)的位置,此时 fast 指向值为 4 的节点的位置,fast 只需要由虚拟头节点的位置 右移 n + 1 = 4 即可。如下图示:

当 fast 右移至值为 4 的节点时,指针 slow 和 fast 同时右移,直至 fast 移到 NULL,此时 slow 刚好到 target 位置,即指向 倒数第 n + 1 个节点,如下图示。

Show me the Code

c++

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* dummyHead = new ListNode(0);
    dummyHead->next = head;
    ListNode *slow = dummyHead, *fast = dummyHead;
    for (int i = 0; i < n + 1; ++i) {
        fast = fast->next;
    }

    while (fast != NULL) {
        slow = slow->next;
        fast = fast->next;
    }

    ListNode* delNode = slow->next;
    slow->next = delNode->next;
    delete delNode;

    ListNode* retNode = dummyHead->next;
    delete dummyHead;

    return retNode;
}

java

ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummyHead = new ListNode(0);
    dummyHead.next = head;
    ListNode slow = dummyHead, fast = dummyHead;
    for (int i = 0; i < n + 1; ++i) {
        fast = fast.next;
    }

    while (fast != null) {
        slow = slow.next;
        fast = fast.next;
    }

    slow.next = slow.next.next;
    return dummyHead.next;
}

往期精彩回顾

虚拟头节点秒杀链表问题

单链表之环形链表

四种方法解决leetcode203. 移除链表元素

字节面试题 leetcode 83. 删除排序链表中的重复元素

面试不可不会的单链表反转

面试不可不会的单链表反转

更多精彩

关注公众号【程序员小熊】,后台回复【算法】或【python】,即可获取高清无码的经典算法或 python 电子书~

为了回馈读者,本公众号不定期会有送礼活动,敬请关注~

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。