有关链表的小技巧，我都给你总结好了

心已赠人 2023-10-05 12:44 47阅读 0赞

### 链表 ###

链表是数据结构里一个很基础但是又很爱考的线性结构，链表的操作相对来说比较简单，但是非常适合考察面试者写代码的能力，以及对 corner case 的处理，还有指针的应用很容易引起 NPE (null pointer exception)。综合以上原因，链表在面试中很重要。

提到链表就不得不提数组，它和数组可以说是数据结构的基础，那么它们最主要的区别在于：

*  数组在物理内存上必须是连续的
 *  链表在物理内存上不需要连续，通过指针连接

所以数组最好的性质就是可以随机访问 random access，有了 index，可以 O(1) 的时间访问到元素。

而链表因为不连续，所以无法 O(1) 的时间定位任意一个元素的位置，那么就只能从头开始遍历。

这就造成了它们之间增删改查上效率的不同。

除此之外，链表本身的结构与数组也是完全不同的。

LinkedList 是由 ListNode 来实现的：

class ListNode {
      int value;
      ListNode next;
    }

结构上长这样：

![format_png][]

这是单向链表，那还有的链表是双向链表，也就是还有一个 previous pointer 指向当前 node 的前一个 node：

class ListNode {
      int value;
      ListNode next;
      ListNode prev;
    }

![format_png 1][]

其实链表相关的题目没有很难的，套路也就这么几个，其中最常考最基础的题目是反转链表，听说微软可以用这道题电面刷掉一半的 candidate，两种方法一遍 bug free 还是不容易的。文章之前已经写过了，点击这里直达复习。

今天我们来说链表中**最主要的 2 个技巧**：**双指针法**和 **dummy node**，相信看完本文后，链表相关的绝大多数题目你都能搞定啦。

### 双指针法 ###

双指针法在很多数据结构和题型中都有应用，在链表中用的最多的还是`快慢指针`。

顾名思义，两个指针一个走得快，一个走得慢，这样的好处就是以不同的速度遍历链表，方便找到目标位置。

常见的问题比如找一个链表的中点，或者判断一个链表是否有环。

#### 例 1：找中点 ####

![format_png 2][]

这题就是给一个链表，然后找到它的中点，如果是奇数个很好办，如果是偶数个，题目要求返回第二个。

比如：

1 -> 2 -> 3 -> 4 -> 5 -> NULL，需要返回 3 这个 ListNode；

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL，需要返回 4 这个 ListNode。

但其实吐槽一下，如果真的要设计一个这样的 API，我更倾向于选择返回偶数个中的第一个中点。

为什么呢？

算法题都是工业生产中一些问题的抽象。比如说我们找中点的目的是为了把这个链表断开，那么返回了 3，我可以断开 3 和 4；但是返回了 4，单向链表我怎么断开 4 之前的地方呢？还得再来一遍，麻烦。

#### Solution ####

##### 方法一、 #####

这题最直观的解法就是可以先求这个链表的长度，然后再走这个长度的一半，得到中点。

class Solution {
        public ListNode middleNode(ListNode head) {
            if(head == null) {
              return null;
            }
    
            int len = 0;
            ListNode current = head;
            while(current != null) {
                len++;
                current = current.next;
            }
    
            len /= 2;
            ListNode result = head;
            while(len > 0) {
                result = result.next;
                len--;
            }
    
            return result;
        }
    }

##### 方法二、快慢指针 #####

我们用两个指针一起来遍历这个链表，每次快指针走 2 步，慢指针走 1 步，这样当快指针走到头的时候，慢指针应该刚好在链表的中点。

class Solution {
        public ListNode middleNode(ListNode head) {
            ListNode slow = head;
            ListNode fast = head;
            while(fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            return slow;
        }
    }

这两个方法孰优孰劣呢？

网上很多说什么方法一过了两遍链表，方法二只过了一遍。

但其实，但是方法二用了两个指针来遍历，所以两个方法过的遍数都是一样的。

**它们最大的区别是：**

**方法一是 offline algorithm，方法二是 online algorithm。**

**公司里的数据量是源源不断的，比如电商系统里总有客户在下单，社交软件里的好友增长是一直在涨的，这些是数据流 data stream，我们是无法计算数据流的长度的。**

**那么 online algorithm 能够给时刻给出当前的结果，不用说等数据全部录入完成后，实际上也录不完。。这是 online algorithm 比 offline algorithm 大大的优势所在。**

更多的解释大家可以参考 stack overflow 的这个问题\[1\]，链接在文末。

![format_png 3][]

#### 例 2：判断单链表是否有环 ####

![format_png 4][]

思路：快慢指针一起从 head 出发，每次快指针走 2 步，慢指针只走 1 步，如果存在环，那么两个指针一定会相遇。

这题是典型的龟兔赛跑，或者说在操场跑圈时，跑的快的同学总会**套圈**跑的慢的。

public class Solution {
        public boolean hasCycle(ListNode head) {
            ListNode slow = head;
            ListNode fast = head;
            while(fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
                if(slow == fast) {
                    return true;
                }
            }
            return false;
        }
    }

这题有个升级版，就是要求返回环的起点。

#### 例 3：返回有环链表的环的起点 ####

![format_png 5][]

这题我感觉不全是个算法题了，还是个数学题哈哈。

先摆出结论：

1.  快慢指针从链表头开始走，相遇的那点，记为 M；
2.  再用 2 个指针，一个从头开始走，一个从 M 开始走，相遇点即为 cycle 的起点。

我们先看抽象出来的图：

假设快慢指针在 M 点第一次相遇，

这里我们设 3 个变量来表示这个链表里的几个重要长度：

*  X：从链表头到环的起点的长度；
 *  Y：从环的起点到 M 点的长度；
 *  Z：从 M 点到环的起点的长度。

注意：因为环是有方向的，所以 Y 并不是 Z。

那其实我们唯一知道的关系就是：快慢指针在 M 点第一次相遇。这也是我们最初假设的关系。

而快慢指针有一个永远不变的真理：快指针走的长度永远是慢指针走的长度的 2 倍。

相遇时快慢指针分别走了多少的长度呢？

*  快指针：X+ Y + 假设走了 k 圈
 *  慢指针：X + Y

那么我们就可以用这个 2 倍的关系，列出下列等式：

2 \* (X + Y) = X + Y + kL

所以 X + Y = kL

而我们注意到：Y + Z = L，那么就能得出 X = Z。

所以当两个指针，一个从头开始走，一个从 M 点开始走时，相遇那点就是环的起点，证毕。

来看下代码吧：

public class Solution {
      public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
          slow = slow.next;
          fast = fast.next.next;
          if (slow == fast) {
            ListNode x = head;
            ListNode y = slow;
            while(x != y) {
              x = x.next;
              y = y.next;
            }
            return x;
          }
        }
        return null;
      }
    }

这题还有个应用，就是找一个特定数组里重复的数字，这里就不展开了，大家感兴趣的去做一下吧～

![format_png 6][]

接下来我们聊聊 dummy node 这个技巧。

### Dummy node ###

Dummy 的中文是“假”的意思，dummy node 大概可以翻译成虚拟节点？有更地道的说法的话还请大家在评论区告诉我呀～

一般来说，dummy node 的用法是在链表的真实 head 的前面加一个指向这个 head 的节点，目的是为了方便操作 head。

对于链表来说，head 是一个链表的灵魂，因为无论是查询还是其他的操作都需要从头开始，俗话说擒贼先擒王嘛，抓住了一个链表的头，就抓住了整个链表。

所以当需要对现有链表的头进行改动时，或者不确定头部节点是哪个，我们可以预先加一个 dummyHead，这样就可以灵活处理链表中的剩余部分，最后返回时去掉这个“假头”就好了。

很多时候 dummy node 不是必须，但是用了会很方便，减少 corner case 的讨论，所以还是非常推荐使用的。

光说不练假把式，我们直接来看题～

#### 例 4：合并两个排好序的链表 ####

![format_png 7][]

这题有很多种解法，比如最直观的就是用两个指针，然后比较大小，把小的接到最终的结果上去。

但是有点麻烦的是，最后的结果不知道到底谁是头啊，是哪个链表的头作为了最终结果的头呢？

这种情况就非常适合用 dummy node。

先用一个虚拟的头在这撑着，把整个链表构造好之后，再把这个假的剔除。

来看代码～

class Solution {
      public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
          return l2;
        }
        if (l2 == null) {
          return l1;
        }
        ListNode dummy = new ListNode(0);
        ListNode ptr = dummy;
        while (l1 != null && l2 != null) {
          if (l1.val < l2.val) {
            ptr.next = l1;
            l1 = l1.next;
          } else {
            ptr.next = l2;
            l2 = l2.next;
          }
          ptr = ptr.next;
        }
        if (l1 == null) {
          ptr.next = l2;
        } else {
          ptr.next = l1;
        }
        return dummy.next;
      }
    }

这题也有升级版，就是合并 k 个排好序的链表。本质上也是一样的，只不过需要重写一下比较器就好了。

#### 例 5：删除节点 ####

![format_png 8][]

这道题的意思是删除链表中某个特定值的节点，可能有一个可能有多个，可能在头可能在尾。

如果要删除的节点在头的时候，新链表的头就不确定了，也有可能是个空的。。此时就很适合用 dummy node 来做，规避掉这些 corner case 的讨论。

那这题的思路就是：用 2 个指针

*  prev：指向当前新链表的尾巴
 *  curr：指向当前正在遍历的 ListNode

如果 curr == 目标值，那就直接移到下一个；

如果 curr != 目标值，那就把 prev 指向它，接上。

这题需要注意的是，最后一定要把 prev.next 指向 null，否则如果原链表的尾巴是目标值的话，还是去不掉。

代码如下：

class Solution {
      public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(0);
        ListNode prev = dummy;
        ListNode curr = head;
        while(curr != null) {
          if (curr.val != val) {
            prev.next = curr;
            prev = prev.next;
          }
          curr = curr.next;
        }
        prev.next = null;
        return dummy.next;
      }
    }

**好了，以上就是本文的所有内容了，如果这篇文章对你有帮助，欢迎分享给你身边的朋友，也给我点个「在看」，你们的支持是我创作的最大动力！**

![format_png 9][]

往期推荐

[![format_png 10][]][format_png 10 1]

[链表反转的两种实现方法，后一种击败了100%的用户！][format_png 10 1]

[![format_png 11][]][format_png 11 1]

[漫画：如何找到链表的倒数第n个结点？][format_png 11 1]

[![format_png 12][]][format_png 12 1]

[算法图解：如何用两个栈实现一个队列？][format_png 12 1]

关注我，每天陪你进步一点点！

![format_png 13][]

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9vZzVyN1BIR0hvaWFnMnRnS0RwOTZTMjFsdFh2YmoyNTZiTTltaFVUWnNxd2hydTFybWViajRjdmdrQ2Y4R3ZxSlppY2dtN3VzWGg1Sk9mVGFjaWJSMkVpY0EvNjQw?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9vZzVyN1BIR0hvaWFnMnRnS0RwOTZTMjFsdFh2YmoyNTZqdFhOMWNEYkg2VmZmN0RobkZrbDl3ZklpYk5CanI0OXkxY09JWTBqcnlzandJVmRqQTF3QmtRLzY0MA?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9vZzVyN1BIR0hvaWFnMnRnS0RwOTZTMjFsdFh2YmoyNTZlVUZjWFpQSWVDMk9QbGpJWkFhM2JXZWU5WHNFSExaejhpYUxyTVFjZmM1OFYyZVpUSjN6WFVBLzY0MA?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9vZzVyN1BIR0hvaWFnMnRnS0RwOTZTMjFsdFh2YmoyNTZjeU12dFNaSElBZWlhNXVGRVpFUW1LTmljYUVpYzFEemNUS0R1dlg2WE94SzZhU1VIMnluOVplTGcvNjQw?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9vZzVyN1BIR0hvaWFnMnRnS0RwOTZTMjFsdFh2YmoyNTY5MVZtNkNvUWdjRG5oblVKdWRHcHFFRkppY3pwV25raWFLbGJzenVpYVRNaWFybW1WUlhiNlZ3a1BnLzY0MA?x-oss-process=image/format,png
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9vZzVyN1BIR0hvaWFnMnRnS0RwOTZTMjFsdFh2YmoyNTZWYXZMd29xS3hZdlNyVEJpYkt2ejN6WWZxMldvZDlDejMzaWJJUnduTUFpYWljS2MzckVwQmphOEpBLzY0MA?x-oss-process=image/format,png
[format_png 6]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9vZzVyN1BIR0hvaWFnMnRnS0RwOTZTMjFsdFh2YmoyNTZKZUF3bHZibExGeFRXRzBtaWM1NnVyNXpOcUhmMzNGNU1OdzJ6dHBOd0hlbEI5ZWJXSU1kNlBRLzY0MA?x-oss-process=image/format,png
[format_png 7]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9vZzVyN1BIR0hvaWFnMnRnS0RwOTZTMjFsdFh2YmoyNTZtd1RCMG04NDlnZEtkVzRTNTE0aWNsclZzY3dKVWhrSVVDUHNpYlE0WjBCQmNkaHp2OHFNYjN5QS82NDA?x-oss-process=image/format,png
[format_png 8]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9vZzVyN1BIR0hvaWFnMnRnS0RwOTZTMjFsdFh2YmoyNTZSMmRiaWNKbHFVd0ZDVmhIMFlHc3VJU3BNZFg1MlliVlpEaWFCaWEwSmtkTGpRbDg1WGljMm1ZT2NRLzY0MA?x-oss-process=image/format,png
[format_png 9]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2dpZi9iOTZDaWJDdDcwaWFid2p5b2pMaEEwM1B0eFVua05QUkVudDJGNDh5d2ZYTHBEZERBamljT1RQSThROTR0VkxiSjU4dGJSczEyaWFYREtoVU9XOWdkNE5sRkEvNjQw?x-oss-process=image/format,png
[format_png 10]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9Icld3Nlp1WENzanJRMWt6ZjZ1cTNoTE1qNG1TQk95Zmh1R3hNd091TVh0WW5iSkFXWDBDOUJqejREcXFPWkpDTjloTXFwOW96SHZ3dk1oNWxiU01YUS82NDA?x-oss-process=image/format,png
[format_png 10 1]: http://mp.weixin.qq.com/s?__biz=MzU1NTkwODE4Mw%3D%3D&chksm=fbcc7519ccbbfc0f847ac650e02419ab813f6a5ea320cc37baac0c227f8fb241990fcbf265bd&idx=1&mid=2247489569&scene=21&sn=ead310b54ef0b51574c34426b0190d87#wechat_redirect
[format_png 11]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3JyaWJ4UW9CY0ZMMUNLMmZqV2FpY0hFbXVidjZzZXJwWTBFWGswaDd3OTRpYzFkWXNaYVlFMmxLVGNNdDZ5eU1OQ3NSc2d5RHppY1YyaWJoUS82NDA?x-oss-process=image/format,png
[format_png 11 1]: http://mp.weixin.qq.com/s?__biz=MzU1NTkwODE4Mw%3D%3D&chksm=fbcc7179ccbbf86f22f4c7d28f57b069b0c03a9cb926eccff3ed38225df3f054e5740551a854&idx=1&mid=2247490625&scene=21&sn=de5bf4f5bb7a4ad1780779f58575725e#wechat_redirect
[format_png 12]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9Icld3Nlp1WENzaDlEdzk0RWxQc2w5QzZwM05vTjBQNzJXeG1Rc3Q0ZEticXpnb25TMktVUFJIYzlQaDl0WGxSeHdpY3BIUVNVeHlQNFJNdnM5MlVrcncvNjQw?x-oss-process=image/format,png
[format_png 12 1]: http://mp.weixin.qq.com/s?__biz=MzU1NTkwODE4Mw%3D%3D&chksm=fbcc700accbbf91c8fcbcbca86487e93940b1512ddaeea6be57d37f4e202f65eb7c4caceaaf5&idx=1&mid=2247490866&scene=21&sn=8c284164c701aff5c7afa669ee7a347c#wechat_redirect
[format_png 13]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9zWnlBSnRpYWVzV2NqajRZNmIyUnNZampPNGNtc0E3OXZKY2RyY080RDZxb2t6V1l6NjQ4S2ZQVFNsSWhCeWVKbGZzQmtLaWFzWHR4a2JSTFRUSUxRcGlidy82NDA?x-oss-process=image/format,png