What is LinkedList? 什么是链表?

LinkedList是一个线性逻辑的结构. 之前有一个国内的朋友要考计算机等级证书, 于是让我给她讲讲什么是链表. 那该怎么给一个非计算机专业的朋友讲清楚呢? 其实现实生活中就有很多链表式的结构, 例如体育老师让一队小朋友重头到尾的报数, 又例如一列火车, 他们都有什么样的特征呢? 链状, 一环扣一环. 那我们下面就用火车来举例:

那我们想想, 一辆火车由什么构成? 是不是一截截的车厢? 那车厢与车厢怎么链接的呢? 是不是由许多链接扣互相扣住的? 那对应的在 LinkedList 里面, 车厢就是 LinkedList 的ListNode 节点, 而链接这些节点的就是每个节点上指向下一个 Node 节点的 Pointer. 车厢里面装了什么东西, 车厢有多少个座位, 或者车厢长宽高有多少, 都对应着 ListNode 的属性, 这个 ListNode 可能有一个 size 的属性, 可能有一个 array 属性表示能放多少东西. 每个 Pointer 则有下一个Node 的地址, 也类似于下一节车厢号, 我们可以顺着这个号码一步一步走到车厢尾. 于是怎么来遍历一个 LinkedList 也就清晰了.

遍历: 每当去坐火车时候, 你到站台后是不是只会站在一个车厢前面, 那你怎么到自己的车厢去呢? 肯定得顺着当前这个车厢一节一节的找下去对吧? 同样的道理, 在 LinkedList 里面, 你往往最开始是站到 LinkedList 的 Header 上面的, 那你怎么找到你要找得 Node 呢, 只有顺着头一步一步, 看看 Pointer 指向的是不是我的Node, 如果是那直接进去就行了, 如果不是呢, 继续穿过这个 Node 找下一个 Node.

增加: 怎么添加车厢呢? 比如 A 车厢指向 B 车厢, 现在你想插一个 C 车厢在 AB 之间, 该怎么做? 是不是第一步要拆开 A-B, 然后把 C的尾巴 跟 B 连在一起, 再把 A 的尾巴跟 C 连在一起. 同样的, 如果给你一个 LinkedList, 第一步是不是得找到 A和 B 节点, 然后按照一样的办法, 把 C 节点插进去.

删除: 好现在 A 在 C 前面, C 在 B 前面, 我想把 C 车厢给推出去, 是不是得把 C 和 B 的扣子解开, 又把 C 和 A 的扣子解开, 然后牵着 A 和 B 的手, 祝福他们爱情恒久.

那有朋友肯定说, 你这样找车厢太慢了呀, 要挨个挨个找, 不能一步就找到吗? 当然有啦, 就像列车员直接告诉你, 车厢在哪你直接去就行了,  我们只需要在雇佣一位 Map 结构”列车员”就行了, 例如 LRU Cache 就能够用这种办法实现.

LinkedList 是一个非常基础却经常用到的数据结构, 那在面试过程中, 往往会有很多题目与之相关, 例如最基本的 Reverse LinkedList, 翻转进阶一点的就是翻转一部分的链表. 还有是 Merge 2 LinkedList 甚至是 Merge K LinkedList.

那除此之外, 在链表题里面, 快慢指针(Fast and Slow pointers)的应用也是非常广泛, 例如下面这道题 LinkedList Cycle,你怎么确定链表里面有一个环呢? 那有环会发生什么? 是不是如果你一直沿着走, 肯定会不断不断绕圈, 那我们利用这个特性, 用很直接的办法, 就是固定一个起点, 然后让另一个朋友一直走, 看到能不能再回到这个起点, 那么就有两个问题了, 一是有可能一直绕呀什么时候是个停呀, 二是固定的起点不一定是在环上呀, 就算我们停了也要重新找一个起点继续绕呀. 这时候快慢指针就派上用场了, 看看下面代码能看出什么鬼吗?

这就是快慢指针的奇妙地方, 那进阶一点的问题, 假如这个链表有环了, 怎么找到环从哪开始的呢?

除此之外, 还有一个解题技巧就是加 Dummy Node, 什么是 Dummy Node 呢? 就是派一个哨兵站岗立一个标杆, 让我每次想对这个链表操作时候我有一个明确的坐标, 例如下面这道题 Remove Duplicates from Sorted List II.

这些小技巧只是帮助你解题更加方便, 或者说提供另一种思路, 但是解决链表题的核心还是在于搞懂链表的构成, 节点与节点之间的链接, 保持增删节点之后链表的一致性.多加练习, 熟能生巧.