专栏首页小浩算法漫画:删除链表倒数第N个节点(二次修订版)

漫画:删除链表倒数第N个节点(二次修订版)

修改版修改内容:

  1. 新增完整解题过程
  2. 优化排版

01

哨兵节点

链表的题目,十道有九道会用到哨兵节点。所以我们先讲一下什么是哨兵节点。

哨兵节点,捞干货,其实就是一个附加在原链表最前面用来简化边界条件的附加节点,它的值域不存储任何东西,只是为了操作方便而引入。

比如原链表为a->b->c,则加了哨兵节点的链表即为x->a->b>c,如下图:

那我们为什么需要引入哨兵节点呢,我举个例子。比如我们要删除某链表的第一个元素,常见的删除链表的操作是找到要删元素的前一个元素,假如我们记为pre。我们通过:

pre.Next = pre.Next.Next

来进行删除链表的操作。但是此时若是删除第一个元素的话,你就很难进行了,因为按道理来讲,此时第一个元素的前一个元素就是nil(空的),如果使用pre就会报错。那如果此时你设置了哨兵节点的话,此时的pre就是哨兵节点了。这样对于链表中的任何一个元素,你要删除都可以通过pre.Next=pre.Next.Next的方式来进行,这就是哨兵节点的作用。

02

题目讲解

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

示例:

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

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

说明:

给定的 n 保证是有效的。

进阶:

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

首先我们思考,让我们删除倒数第N个元素,那我们只要找到倒数第N个元素就可以了,那怎么找呢?我们只需要设置两个指针变量,中间间隔N-1元素。当后面的指针遍历完所有元素指向nil时,前面的指针就指向了我们要删除的元素。如下图所示:

03

完整解题过程

现在我们来完整捋一遍解题过程:

  1. 首先我们定义好哨兵节点result,指向哨兵节点的目标元素指针cur,以及目标指针cur的前一个指针pre,此时pre指向nil。
  2. 接下来我们开始遍历整个链表。
  3. 当head移动到距离目标元素cur的距离为N-1时,同时开始移动cur。
  4. 当链表遍历完之后,此时head指向nil,这时的cur就是我们要找的待删除的目标元素。
  5. 最后我们通过pre.Next = pre.Next.Next完成删除操作,就完成了整个解题过程。

04

话不多说,看代码

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    result := &ListNode{}
    result.Next = head
    var pre *ListNode
    cur := result
    i := 1
    for head != nil {
        if i >= n {
            pre = cur
            cur = cur.Next
        }
        head = head.Next
        i++
    }
    pre.Next = pre.Next.Next
    return result.Next
}

注:本系列所有教程中都不会用到复杂的语言特性,大家不需要担心没有学过go。算法思想最重要,使用go纯属本人爱好。同时,本系列所有代码均在leetcode上进行过测试运行,保证其严谨性!

本文分享自微信公众号 - 小浩算法(xuesuanfa),作者:程序员浩哥

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-01-20

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 《剑指offer》第23天:删除链表倒数第N个节点

    哨兵节点,其实就是一个附加在原链表最前面用来简化边界条件的附加节点,它的值域不存储任何东西,只是为了操作方便而引入。

    程序员小浩
  • 漫画:如何合并两个有序链表

    第21题:将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

    程序员小浩
  • 漫画:反转字符串

    今天是初一,因为新型肺炎外出的活动基本都取消了,待在家里学习看书陪陪家人。希望大家也提高意识,能不出门就尽量别出了!

    程序员小浩
  • 《剑指offer》第23天:删除链表倒数第N个节点

    哨兵节点,其实就是一个附加在原链表最前面用来简化边界条件的附加节点,它的值域不存储任何东西,只是为了操作方便而引入。

    程序员小浩
  • JavaScript 高级函数

    用 reduce 则用 很少 的代码解决,尤其是采用了 ==es6== 语法后,更加简单

    Karl Du
  • C# TreeView使用技巧

    代码中对事件参数e.Action的判断,可以避免在改变节点的Checked的状态时,再次进入AfterCheck(),这样当在AfterCheck()中有其他逻...

    跟着阿笨一起玩NET
  • UOJ#52. 【UR #4】元旦激光炮(交互)

    一种很显然的$log^2n$的做法:首先在$a$中二分,然后再$b,c$中二分。这样可以得到$60$分的好成绩。

    attack
  • 小朋友学数据结构1:链表

    链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以...

    海天一树
  • 你没中过勒索病毒,不知道备份有多重要

    今天是春节放假前的最后一天,照例对自己一些数据开始进行了备份。突然想到关于数据备份有些心得想要分享下,于是写了这篇文章。

    twowinter
  • Laravel5.8使用LayUI上传并显示图片操作

    这个问题已经困扰好久了,唉 比较难受,本来学习laravel使用的是Bootstrap,之后用的是Uploadify进行上传图片,无奈,这个技术需要Flash的...

    Debug客栈

扫码关注云+社区

领取腾讯云代金券