数据结构与算法之美
王争
前Google工程师
立即订阅
71638 人已学习
课程目录
已完结 75 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 从今天起,跨过“数据结构与算法”这道坎
免费
入门篇 (4讲)
01 | 为什么要学习数据结构和算法?
02 | 如何抓住重点,系统高效地学习数据结构与算法?
03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?
04 | 复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度
基础篇 (38讲)
05 | 数组:为什么很多编程语言中数组都从0开始编号?
06 | 链表(上):如何实现LRU缓存淘汰算法?
07 | 链表(下):如何轻松写出正确的链表代码?
08 | 栈:如何实现浏览器的前进和后退功能?
09 | 队列:队列在线程池等有限资源池中的应用
10 | 递归:如何用三行代码找到“最终推荐人”?
11 | 排序(上):为什么插入排序比冒泡排序更受欢迎?
12 | 排序(下):如何用快排思想在O(n)内查找第K大元素?
13 | 线性排序:如何根据年龄给100万用户数据排序?
14 | 排序优化:如何实现一个通用的、高性能的排序函数?
15 | 二分查找(上):如何用最省内存的方式实现快速查找功能?
16 | 二分查找(下):如何快速定位IP对应的省份地址?
17 | 跳表:为什么Redis一定要用跳表来实现有序集合?
18 | 散列表(上):Word文档中的单词拼写检查功能是如何实现的?
19 | 散列表(中):如何打造一个工业级水平的散列表?
20 | 散列表(下):为什么散列表和链表经常会一起使用?
21 | 哈希算法(上):如何防止数据库中的用户信息被脱库?
22 | 哈希算法(下):哈希算法在分布式系统中有哪些应用?
23 | 二叉树基础(上):什么样的二叉树适合用数组来存储?
24 | 二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?
25 | 红黑树(上):为什么工程中都用红黑树这种二叉树?
26 | 红黑树(下):掌握这些技巧,你也可以实现一个红黑树
27 | 递归树:如何借助树来求解递归算法的时间复杂度?
28 | 堆和堆排序:为什么说堆排序没有快速排序快?
29 | 堆的应用:如何快速获取到Top 10最热门的搜索关键词?
30 | 图的表示:如何存储微博、微信等社交网络中的好友关系?
31 | 深度和广度优先搜索:如何找出社交网络中的三度好友关系?
32 | 字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配?
33 | 字符串匹配基础(中):如何实现文本编辑器中的查找功能?
34 | 字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?
35 | Trie树:如何实现搜索引擎的搜索关键词提示功能?
36 | AC自动机:如何用多模式串匹配实现敏感词过滤功能?
37 | 贪心算法:如何用贪心算法实现Huffman压缩编码?
38 | 分治算法:谈一谈大规模计算框架MapReduce中的分治思想
39 | 回溯算法:从电影《蝴蝶效应》中学习回溯算法的核心思想
40 | 初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?
41 | 动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题
42 | 动态规划实战:如何实现搜索引擎中的拼写纠错功能?
高级篇 (9讲)
43 | 拓扑排序:如何确定代码源文件的编译依赖关系?
44 | 最短路径:地图软件是如何计算出最优出行路径的?
45 | 位图:如何实现网页爬虫中的URL去重功能?
46 | 概率统计:如何利用朴素贝叶斯算法过滤垃圾短信?
47 | 向量空间:如何实现一个简单的音乐推荐系统?
48 | B+树:MySQL数据库索引是如何实现的?
49 | 搜索:如何用A*搜索算法实现游戏中的寻路功能?
50 | 索引:如何在海量数据中快速查找某个数据?
51 | 并行算法:如何利用并行处理提高算法的执行效率?
实战篇 (5讲)
52 | 算法实战(一):剖析Redis常用数据类型对应的数据结构
53 | 算法实战(二):剖析搜索引擎背后的经典数据结构和算法
54 | 算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法
55 | 算法实战(四):剖析微服务接口鉴权限流背后的数据结构和算法
56 | 算法实战(五):如何用学过的数据结构和算法实现一个短网址系统?
加餐:不定期福利 (6讲)
不定期福利第一期 | 数据结构与算法学习书单
不定期福利第二期 | 王争:羁绊前行的,不是肆虐的狂风,而是内心的迷茫
不定期福利第三期 | 测一测你的算法阶段学习成果
不定期福利第四期 | 刘超:我是怎么学习《数据结构与算法之美》的?
总结课 | 在实际开发中,如何权衡选择使用哪种数据结构和算法?
《数据结构与算法之美》学习指导手册
加餐:春节7天练 (7讲)
春节7天练 | Day 1:数组和链表
春节7天练 | Day 2:栈、队列和递归
春节7天练 | Day 3:排序和二分查找
春节7天练 | Day 4:散列表和字符串
春节7天练 | Day 5:二叉树和堆
春节7天练 | Day 6:图
春节7天练 | Day 7:贪心、分治、回溯和动态规划
加餐:用户学习故事 (2讲)
用户故事 | Jerry银银:这一年我的脑海里只有算法
用户故事 | zixuan:站在思维的高处,才有足够的视野和能力欣赏“美”
结束语 (3讲)
结束语 | 送君千里,终须一别
第2季回归 | 这一次,我们一起拿下设计模式!
打卡召集令 | 60 天攻克数据结构与算法
免费
数据结构与算法之美
登录|注册

07 | 链表(下):如何轻松写出正确的链表代码?

王争 2018-10-05
上一节我讲了链表相关的基础知识。学完之后,我看到有人留言说,基础知识我都掌握了,但是写链表代码还是很费劲。哈哈,的确是这样的!
想要写好链表代码并不是容易的事儿,尤其是那些复杂的链表操作,比如链表反转、有序链表合并等,写的时候非常容易出错。从我上百场面试的经验来看,能把“链表反转”这几行代码写对的人不足 10%。
为什么链表代码这么难写?究竟怎样才能比较轻松地写出正确的链表代码呢?
只要愿意投入时间,我觉得大多数人都是可以学会的。比如说,如果你真的能花上一个周末或者一整天的时间,就去写链表反转这一个代码,多写几遍,一直练到能毫不费力地写出 Bug free 的代码。这个坎还会很难跨吗?
当然,自己有决心并且付出精力是成功的先决条件,除此之外,我们还需要一些方法和技巧。我根据自己的学习经历和工作经验,总结了几个写链表代码技巧。如果你能熟练掌握这几个技巧,加上你的主动和坚持,轻松拿下链表代码完全没有问题。

技巧一:理解指针或引用的含义

事实上,看懂链表的结构并不是很难,但是一旦把它和指针混在一起,就很容易让人摸不着头脑。所以,要想写对链表代码,首先就要理解好指针。
我们知道,有些语言有“指针”的概念,比如 C 语言;有些语言没有指针,取而代之的是“引用”,比如 Java、Python。不管是“指针”还是“引用”,实际上,它们的意思都是一样的,都是存储所指对象的内存地址。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《数据结构与算法之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(332)

  • zeta 置顶
    建议大家在实现之前的思考时间不要太长。一是先用自己能想到的暴力方法实现试试。另外就是在一定时间内(比如半个到一个小时)实在想不到就要在网上搜搜答案。有的算法,比如链表中环的检测,的最优解法还是挺巧妙的,一般来说不是生想就能想到的

    作者回复: 👍,高手!实际上,写链表代码还是主要为了锻炼写代码的能力,倒不是思考解决办法。像环的检测这种解决办法我也想不出来,都是看了答案之后恍然大悟。

    2018-10-06
    7
    285
  • 0xFFFFFFFF
    练习题LeetCode对应编号:206,141,21,19,876。大家可以去练习,另外建议作者兄每章直接给出LC的题目编号或链接方便大家练习。

    作者回复: 我可以集中写一篇练习题的。现在这种思考题的方式是早就定好的了。不好改了。

    2018-10-06
    2
    395
  • 姜威
    总结:如何优雅的写出链表代码?6大学习技巧

    一、理解指针或引用的含义
    1.含义:将某个变量(对象)赋值给指针(引用),实际上就是就是将这个变量(对象)的地址赋值给指针(引用)。
    2.示例:
    p—>next = q; 表示p节点的后继指针存储了q节点的内存地址。
    p—>next = p—>next—>next; 表示p节点的后继指针存储了p节点的下下个节点的内存地址。

    二、警惕指针丢失和内存泄漏(单链表)
    1.插入节点
    在节点a和节点b之间插入节点x,b是a的下一节点,,p指针指向节点a,则造成指针丢失和内存泄漏的代码:p—>next = x;x—>next = p—>next; 显然这会导致x节点的后继指针指向自身。
    正确的写法是2句代码交换顺序,即:x—>next = p—>next; p—>next = x;
    2.删除节点
    在节点a和节点b之间删除节点b,b是a的下一节点,p指针指向节点a:p—>next = p—>next—>next;

    三、利用“哨兵”简化实现难度
    1.什么是“哨兵”?
    链表中的“哨兵”节点是解决边界问题的,不参与业务逻辑。如果我们引入“哨兵”节点,则不管链表是否为空,head指针都会指向这个“哨兵”节点。我们把这种有“哨兵”节点的链表称为带头链表,相反,没有“哨兵”节点的链表就称为不带头链表。
    2.未引入“哨兵”的情况
    如果在p节点后插入一个节点,只需2行代码即可搞定:
    new_node—>next = p—>next;
    p—>next = new_node;
    但,若向空链表中插入一个节点,则代码如下:
    if(head == null){
    head = new_node;
    }
    如果要删除节点p的后继节点,只需1行代码即可搞定:
    p—>next = p—>next—>next;
    但,若是删除链表的最有一个节点(链表中只剩下这个节点),则代码如下:
    if(head—>next == null){
    head = null;
    }
    从上面的情况可以看出,针对链表的插入、删除操作,需要对插入第一个节点和删除最后一个节点的情况进行特殊处理。这样代码就会显得很繁琐,所以引入“哨兵”节点来解决这个问题。
    3.引入“哨兵”的情况
    “哨兵”节点不存储数据,无论链表是否为空,head指针都会指向它,作为链表的头结点始终存在。这样,插入第一个节点和插入其他节点,删除最后一个节点和删除其他节点都可以统一为相同的代码实现逻辑了。
    4.“哨兵”还有哪些应用场景?
    这个知识有限,暂时想不出来呀!但总结起来,哨兵最大的作用就是简化边界条件的处理。

    四、重点留意边界条件处理
    经常用来检查链表是否正确的边界4个边界条件:
    1.如果链表为空时,代码是否能正常工作?
    2.如果链表只包含一个节点时,代码是否能正常工作?
    3.如果链表只包含两个节点时,代码是否能正常工作?
    4.代码逻辑在处理头尾节点时是否能正常工作?

    五、举例画图,辅助思考
    核心思想:释放脑容量,留更多的给逻辑思考,这样就会感觉到思路清晰很多。

    六、多写多练,没有捷径
    5个常见的链表操作:
    1.单链表反转
    2.链表中环的检测
    3.两个有序链表合并
    4.删除链表倒数第n个节点
    5.求链表的中间节点
    2018-10-05
    1
    164
  • optvxq
    哨兵可以理解为它可以减少特殊情况的判断,比如判空,比如判越界,比如减少链表插入删除中对空链表的判断,比如例子中对i越界的判断。

    空与越界可以认为是小概率情况,所以代码每一次操作都走一遍判断,在大部分情况下都会是多余的。

    哨兵的巧妙就是提前将这种情况去除,比如给一个哨兵结点,以及将key赋值给数组末元素,让数组遍历不用判断越界也可以因为相等停下来。

    使用哨兵的指导思想应该是将小概率需要的判断先提前扼杀,比如提前给他一个值让他不为null,或者提前预设值,或者多态的时候提前给个空实现,然后在每一次操作中不必再判断以增加效率。
    2018-10-10
    3
    96
  • Rain
    谢谢老师,这节课又学到了,写完留言我要去思考那几个问题了,一个都不会。。

    ----

    文中提到,

    但是,如果我们要删除链表中的最后一个结点,前面的删除代码就不 work 了。跟插入类似,我们也需要对于这种情况特殊处理。写成代码是这样子的:

    if (head->next == null) {
       head = null;
    }

    ----

    感觉此处代码处理的是当链表中只有表头一个节点的删除情况,而不是"要删除链表中的最后一个结点"的情况。是不是head应该改成p?
    2018-10-05
    3
    57
  • zyzheng
    一直对手写链表代码有恐惧心理,这次硬着头皮也要迈过这个坎
    2018-10-05
    48
  • 千方残光
    /**
    public class Node {
    public char c;
    public Node next;

    public Node(char c) {
    this.c = c;
    }
    }
    **/

    public static Node reverse(Node head) {
    if(head == null || head.next == null) {
    return head;
    }

    Node prev = null;
    Node cur = head;
    Node next = head.next;

    while(next != null) {
    cur.next = prev;
    prev = cur;
    cur = next;
    next = cur.next;
    }
    cur.next = prev;
    return cur;
    }


    public static boolean existsCircle(Node head) {
    Node slow = head;
    Node fast = head;
    while(fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
    if(slow == fast) {
    return true;
    }
    }
    return false;
    }

    public static Node merge(Node head1, Node head2) {

    Node guard = new Node('/');
    Node cur = guard;

    while(head1 != null && head2 != null) {
    if(head1.c <= head2.c) {
    while(head1 != null && head1.c <= head2.c) {
    cur.next = head1;
    cur = cur.next;
    head1 = head1.next;

    }
    } else {
    while(head2 != null && head1.c > head2.c) {
    cur.next = head2;
    cur = cur.next;
    head2 = head2.next;

    }
    }
    }

    if(head1 != null) {
    cur.next = head1;
    }
    if(head2 != null) {
    cur.next = head2;
    }

    return guard.next;

    }

    public static Node deleteLastN(Node head, int n) {
    if(n < 1 || head == null) {
    return head;
    }
    Node guard = new Node('/');
    guard.next = head;

    Node slow = guard;
    Node fast = guard;

    for(int i = 0; i < n; i++) {
    if(fast != null) {
    fast = fast.next;
    }
    }
    while(fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next;
    }
    slow.next = slow.next.next;
    return guard.next;
    }

    public static Node getMiddle(Node head, int n) {
    Node slow = head;
    Node fast = head;

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

    return slow;
    }
    2018-10-09
    2
    44
  • 五岳寻仙
    老师您好!请教您一个问题。在学习了数组和链表之后,想知道在现实应用中有没有将二者结合起来的情况。
    比如,我想用数组存储数据,但数组大小提前无法知道,如果使用动态数组的话,中间涉及到数组拷贝;如果使用链表的话,每增加一个元素都要malloc一次(频繁的malloc会不会影响效率并且导致内存碎片?)。
    可不可以用链表将数组链接起来?也就是说链表里每个node存储了数组指针,这样每增加一个节点就可以多存放很多元素。如果可以的话,与直接使用动态数组或者直接使用链表比有没有什么优缺点,为何在网上搜索几乎找不到人这样用?

    作者回复: 👍 思考的深入 你说的这个很像内存池 你可以百度一下看看是不是你想要的

    2018-10-07
    10
    43
  • 小喵喵
    学习了好几节数据结构和算法了,我是也CRUD业务代码的,感觉还是用不着啊?

    作者回复: 1. 建议再看下“为什么要学习数据结构和算法”那节课,包括里面的留言,有很多留言都写的很好,很多人都对这门课有比较清晰深刻的认识。
    2. 你的疑问应该是:局限于你现在的工作,你觉得用不上对吧。这个是很有可能的。如果你做的项目都是很小的项目,也没有什么性能压力,平时自己也不去思考非功能性的需求,只是完成业务代码就ok了,那确实感觉用不到。但这是你个人的原因,并不代表就真用不到呢,兄弟!
    3. 专栏里有很多贴近开发的内容,比如链表这一节,我就讲了LRU算法。数组这一节,我讲了容器和数组的选择。复杂度这一节,我讲了如何预判代码的性能。这些都是很贴合开发的。
    4. 我尽量将内容贴近实际的开发,但并不代表一定贴近你的CRUD开发。知识如何用到你的项目中,需要你自己根据我的文章举一反三的思考。

    2018-10-05
    2
    32
  • 来自地狱的勇士
    问题一:文中提到,指针丢失会导致内存泄露,老师能解释下如何导致的内存泄露吗?
    问题二:讲哨兵那块的内容时,说代码二比代码一成功省掉了一次比较i<n,这句不大理解,代码二中,while的条件a[i]!=key也是在比较吧?
    2018-10-05
    7
    30
  • 匆匆
    关于练习链表的一点体会

    1、 函数中需要移动链表时,最好新建一个指针来移动,以免更改原始指针位置。

    2、 单链表有带头节点和不带头结点的链表之分,一般做题默认头结点是有值的。

    3、 链表的内存时不连续的,一个节点占一块内存,每块内存中有一块位置(next)存放下一节点的地址(这是单链表为例)。

    3、 链表中找环的思想:创建两个指针一个快指针一次走两步一个慢指针一次走一步,若相遇则有环,若先指向nullptr则无环。

    4、 链表找倒数第k个节点思想:创建两个指针,第一个先走k-1步然后两个在一同走。第一个走到最后时则第二个指针指向倒数第k位置。

    5、 反向链表思想:从前往后将每个节点的指针反向,即.next内的地址换成前一个节点的,但为了防止后面链表的丢失,在每次换之前需要先创建个指针指向下一个节点。

    6、 两个有序链表合并思想:这里用到递归思想。先判断是否有一个链表是空链表,是则返回两一个链表,免得指针指向不知名区域引发程序崩溃。然后每次比较两个链表的头结点,小的值做新链表的头结点,此节点的next指针指向本函数(递归开始,参数是较小值所在链表.next和另一个链表)。
    2018-12-02
    1
    29
  • gogo
    c语言不熟悉 看起来有点吃力

    作者回复: 不好意思 我尽量写简单点 多加点注释

    2018-10-05
    16
  • 王振华 程序员 区块链
    但是,如果我们要删除链表中的最后一个结点,前面的删除代码就不work了。
    ```
    if (head->next == null) {
        head = null
    }
    ```
    这里的head表示的是最后一个结点吗?

    “对于带头链表,插入头结点和插入其它节点,可以统一为相同的逻辑。”这我可以理解

    但即使是带头链表,删除尾结点和删除其它节点,还是不能统一代码呀。

    `p->next = p->next->next;` 无论是否是带头链表,对尾结点都没有影响呀。这行代码还是不能用于尾结点的删除呀?

    作者回复: 你理解错我的意思了。我说的最后一个结点的意思是:链表中只剩下一个结点。并不是指尾结点。

    2018-10-06
    6
    14
  • 失火的夏天
    1.三个节点p.pre,p,p.next,将p的next指针指向p.pre,然后p.pre=p,p=p.next,p.next=p.next.next移动指针,就可以实现单链表反转。
    2.最简单就是一个节点在头,一个节点一直遍历,地址相等就是环,不过好像还有一种简单的办法,快慢前进,一次就能搞定。这个老师能不能说下自己的思路,我有点想不明白。
    3.建立第三个链表,每次比较a链表当前节点和b链表当前节点的大小。如果a比b小,则c的next指针指向a当前节点,c=c.next,然后a指针后移。接着继续比较a.b当前节点大小,反之则把a换成b就行了。
    4.一个p节点,然后找到距离p有n个next节点的点,一起往后遍历,到pn.next为空的时候,p就是我们要求的那个地址。
    5.快慢指针,一个每次前进2个节点一个每次前进1节点。前进两个节点到表尾的时候,前进一个的就是中间点。
    2018-10-05
    4
    13
  • Smallfly
    如何写好链表代码?

    1. 理解指针或引用的含义
    什么是指针?指针是一个变量,该变量中存的是其它变量的地址。将普通变量赋值给指针变量,其实是把它的地址赋值给指针变量。

    2. 警惕指针丢失和内存泄漏
    在插入和删除结点时,要注意先持有后面的结点再操作,否者一旦后面结点的前继指针被断开,就无法再访问,导致内存泄漏。

    3. 利用哨兵简化难度
    链表的插入、删除操作,需要对插入第一个结点和删除最后一个节点做特殊处理。利用哨兵对象可以不用边界判断,链表的哨兵对象是只存指针不存数据的头结点。

    4. 重点留意边界条件处理
    操作链表时要考虑链表为空、一个结点、两个结点、头结点、尾结点的情况。学习数据结构和算法主要是掌握一系列思想,能在其它的编码中也养成考虑边界的习惯。

    5. 举例画图,辅助思考
    对于比较复杂的操作,可以用纸笔画一画,释放脑容量来做逻辑处理(时间换空间思想),也便于完成后的检查。

    6. 多写多练,没有捷径
    孰能生巧,不管是什么算法,只有经过反复的练习,才能信手拈来。


    哨兵对象思想,在 iOS AutoreleasePool 中有用到,在 AutoreleasePoolPush 时添加一个哨兵对象,Pop 时将到哨兵对象之间的所有 Autorelease 对象发送 release 消息。
    2018-10-05
    12
  • 鲫鱼
    快哭了,跨专业学习,就自学了一点python。都不知道要怎么去理解了😭
    但是还是能理解一点的,慢慢坑了

    作者回复: 买本大话数据结构或者算法图解结合着看吧 这门课本身就比较难学 只能多花点时间了呢

    2018-10-09
    10
  • Miletos
    C语言,二级指针可以绕过不带头结点链表删除操作的边界检查。
    2018-10-05
    9
  • hope
    看完了,打卡,稍后手写作业,去GitHub上看了下 ,希望老师把c的代码也添加上,谢谢

    作者回复: 要不你写下 提个pull request?

    2018-10-05
    8
  • 广进
    作为一个小白,每节课都有看不懂的,这次又来了,那个代码二,从while往下就不懂了,怎么感觉和一的功能不一样了。求指导。

    还有您都觉得二可读性差了,加点注释照顾照顾我们这些小白呀。😭

    作者回复: 不好意思 我以后多加点注释 不过两段代码的功能是一样的

    2018-10-05
    6
  • 莫弹弹
    代码二示例返回值int是不是写成inf了哈哈哈

    算法设计思路应该是
    // 用来找出给定key在数组中的下标,找不到则返回-1

    a是被遍历的数组
    n是数组长度
    key是要寻找的值

    1, 判断尾节点是不是要寻找的值,是的话返回n-1,因为数组下标从0开始所以要长度-1才是下标

    2, 使用哨兵变量保存尾节点

    3, 把key放到尾节点,让key成为数组中最后一个值,这样做是为了下一步的遍历

    4, 开始从头开始遍历数组,i为数组下标,如果找到与key相等的元素则退出遍历,否则遍历整个数组

    5, 如果i是尾节点下标,说明没有找到key,如果不是则i为寻找的节点下标,返回i

    6, 把哨兵变量还原赋值到数组尾节点,也就是还原数组

    也就是说平时用的临时变量就是哨兵变量
    2018-10-06
    5
收起评论
99+
返回
顶部