手撕面试算法题必备技巧(贰) —— 双指针(链表篇)_链表双指针

本文介绍了双指针技巧在链表、数组以及字符串中的使用，给出了大量大厂常见面试手撕题目的思路及代码，不仅适合完全不了解双指针技巧的读者，也适合老司机复习拓展。

考察过该技巧的公司有阿里巴巴、腾讯、美团、拼多多、百度等大厂。

我相信，友好的讨论交流会让彼此快速进步！文章难免有疏漏之处，十分欢迎大家在评论区中批评指正。

食用指南： ⭐️为一刷必做题，便于快速理解双指针技巧；无星题目可在刷完⭐️题目后再做，用于拓展学习双指针技巧如何与其他算法知识结合使用。

双指针技巧是什么？

双指针技巧指的就是在遍历链表、数组或者字符串的过程中，不是使用一个指针来进行访问，而是使用两个指针（甚至可以多个，合并 k 个有序链表中将会用到）进行遍历访问。

以链表为例，两个指针要么同方向访问两个链表、要么同方向访问一个链表（快慢指针）、要么相反方向遍历一个链表（左右指针），数组和字符串也是如此。

下面，先来看看双指针技巧在链表问题中的应用。我们以题目入手，从易到难，逐步感受双指针技巧的精妙之处。

几乎所有题目都提供了使用双指针技巧的思路，以及动画示意图，希望可以通过这一篇文章让你彻底弄懂双指针技巧。

双指针秒杀链表问题

⭐️合并两个有序链表(力扣21)

题目描述

思路(双指针)

题目中两个链表已经排好序，我们可以使用两个指针同向访问两个链表，每次比较两个指针的元素，谁小谁加到新的链表上。

参考代码

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
   
    // 一条链表为空，必然返回另一条链表，即使另一条链表也为空
    if (list1 == null) {
   
        return list2;
    }
    if (list2 == null) {
   
        return list1;
    }
    // 新建一个虚拟头节点(新链表)，后面连接两条链表排序后的节点
    ListNode dummy = new ListNode(-1);
    // 三个指针分别指向虚拟头节点，list1，list2
    ListNode p = dummy, p1 = list1, p2 = list2;
    // 当两条链表都不为空的时候遍历
    while (p1 != null && p2 != null) {
   
        // 小的节点加在新链表后面
        if (p1.val <= p2.val) {
   
            p.next = p1;
            // 只移动取值的指针
            p1 = p1.next;
            // 新链表指针也要移动
            p = p.next;
        } else {
   
            p.next = p2;
            // 只移动取值的指针
            p2 = p2.next;
            // 新链表指针也要移动
            p = p.next;
        }
    }
    // 哪条链表有剩余(剩余的值一定比前面都大)，就直接连在新链表后面。
    if (p1 != null) {
   
        p.next = p1;
    }
    if (p2 != null) {
   
        p.next = p2;
    }
    // 返回时去掉虚拟头结点
    return dummy.next;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

Tips

虚拟头节点，即代码中的 dummy 节点。使用虚拟头节点可以避免处理指针 p 为空的情况，降低代码的复杂性。

当我们需要创造一条新链表的时候，可以使用虚拟头节点简化边界情况的处理。 比如本题中两条链表要合并成一条新的有序链表，这时需要创造一条新链表就可以使用。再比如要将一条链表分解成两条链表，这时候要创建两条新链表，也可以使用。

时间复杂度

$O(n)$

最坏情况下，遍历两个链表一共 2 * N 个节点

空间复杂度

$O(1)$

无额外辅助空间，返回的链表是原有节点组装，是必要空间。

---

⭐️分隔链表(力扣86)

题目描述

思路(双指针)

在上一题中，合并两个有序链表，是将两个有序链表合二为一。而本题是将原链表一分为二，然后再合并成一条链表。具体来说，就是将原链表分成两条小链表，一条链表的元素都小于 x，另一条链表中的元素都大于等于 x，最后将两条链表再拼接到一起就可以了。两条小链表的构建过程就需要用到**「双指针」**技巧。

参考代码

public ListNode partition(ListNode head, int x) {
   
    if (head == null) {
   
        return head;
    }
    // 存放小于 x 的链表的虚拟头节点
    ListNode dummyLess = new ListNode(-1);
    // 存放大于等于 x 的链表的虚拟头节点
    ListNode dummyMore = new ListNode(-2);
    // p 指针负责遍历原链表，pLess 负责生成小于 x 的结果链表，pMore 负责生成大于等于 x 的结果链表
    ListNode p = head, pLess = dummyLess, pMore = dummyMore;
    while (p != null) {
    // 原链表不为空
        if (p.val < x) {
   
            pLess.next = p;
            pLess = pLess.next;    
        } else {
   
            pMore.next = p;
            pMore = pMore.next;
        }
        // !!! 如果不断开，会成环报错，新手务必注意！
        // 断开原链表中的每个节点的 next 指针
        ListNode nxt = p.next; // 记录原链表中当前节点的下个节点
        p.next = null; // 当前节点的 next 指针设为空
        p = nxt;
    }
    // 小 x 链表连接大 x 链表
    pLess.next = dummyMore.next;
    // 返回时去掉虚拟头结点
    return dummyLess.next;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

Tips

在循环代码块中，必须断开原链表中每个节点的 next 指针，即将原链表节点的 next 指针设为 null，然后才能向后移动指针，否则就会连接成环从而导致答案错误。

时间复杂度

$O(n)$

最坏情况下，需要完整遍历一遍原链表。

空间复杂度

$O(1)$

使用了常数个指针，没有额外辅助空间。

---

合并 K 个升序链表(力扣23)

题目描述

思路(k个指针)

我们可以准备 k 个指针，分别放在 k 个链表头，每次取出最小的元素，加入到新的大链表中，指针后移，继续比较，每次出去的都是最小元素，就完成了题目的要求。

在 Java 中，我们可以借助优先级队列 PriorityQueue 来实现。优先级队列本质上是一种堆排序容器，根据传入的比较器确定是大根堆还是小根堆，默认是小根堆。小根堆的堆顶是容器中最小的元素，其余更大的元素在堆下方。想要了解这种结构，可以访问 Data Structure Visualizations 网站去查看小根堆的排序过程。

参考代码

public ListNode mergeKLists(ListNode[] lists) {
   
    // 判空
    if (lists == null || lists.length == 0) {
   
        return null;
    }
    // 优先级队列，小根堆
    PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
    // 将 k 个链表的头节点加入小根堆
    for (ListNode head : lists) {
   
        // 头节点不为空才能加入
        if (head != null)
            pq.add(head);
    }
    // 要新建一个结果链表，所以新建一个虚拟头节点，指针 p 用于构建结果链表
    ListNode dummy = new ListNode(-1), p = dummy;
    while (!pq.isEmpty()) {
   
        // 取出最小元素的节点
        ListNode cur = pq.poll();
        // 连接到结果链表上
   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23