稀有猿诉

十年磨一剑，历炼出锋芒，说话千百句，不如码二行。

链表问题总结

链表LinkedList是一种线性的非连续数据结构，优势是随机删除和添加特别高效，但随机访问效率差。因为链表边界条件较多，容易出错，所以还是比较常见的一类题目。但链表常见的问题就那么多，总结起来就那么几个，想要掌握还是比较容易的。

单链表

单链表是出现频率最高的，虽然现实中很少用它，因为它的效率差，现实中一般多用双向链表。单链表也即是每个节点只有一个指针，指向下一个节点，只能从前往后的顺序来遍历，如果想对某一个节点进行操作，必须找到这个节点的前一个节点。

哨兵节点

哨兵节点是指在输入的头节点的前面加一个节点，它的值没有任何意义，它的存在是为了简化逻辑。通常用于添加和删除操作中，如果输入的头节点是null，那么就需要特殊处理，而用了哨兵节点，就可以简化逻辑。

比如说，常规的添加和删除：

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

public static ListNode normalAppend(ListNode head, int value) {
    ListNode newNode = new ListNode(value);
    // ugly
    if (head == null) {
        return newNode;
    }

    ListNode current = head;
    while (current.next != null) {
        current = current.next;
    }

    current.next = newNode;
    return head;
}

public static ListNode normalDelete(ListNode head, int value) {
    // ugly
    if (head == null) {
        return null;
    }
    // ugly
    if (head.val == value) {
        return head.next;
    }

    ListNode current = head;
    while (current.next != null) {
        if (current.next.val == value) {
            current.next = current.next.next;
            break;
        }
        current = current.next;
    }

    return head;
}

可以看到为了处理头节点是null的情况要加很多逻辑，但如果使用哨兵节点，逻辑就会非常简单：

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

public static ListNode append(ListNode head, int value) {
    ListNode dummy = new ListNode(0, head);

    ListNode current = dummy;
    while (current.next != null) {
        current = current.next;
    }
    current.next = new ListNode(value);
    return dummy.next;
}

public static ListNode delete(ListNode head, int value) {
    ListNode dummy = new ListNode(0, head);

    ListNode current = dummy;
    while (current.next != null) {
        if (current.next.val == value) {
            current.next = current.next.next;
            break;
        }
        current = current.next;
    }

    return dummy.next;
}

哨兵节点的作用是要能简化逻辑，一般用在需要考虑头节点为null的情况，或者当使用双指针，需要从-1位置出发时。但不要滥用，要真能起到简化逻辑才可以。另外就是注意哨兵节点的值要尽可能与常规节点的值区分开来，否则把哨兵节点当成常规节点就会出错。

反转

链表反转是基础的操作，有三种方式：迭代，逆向构造式；借助栈，顺向构建；和递归式，详见206的题解。

题目 题解 说明
206. 反转链表 题解
234. 回文链表 题解
题解


遍历和随机访问

主要是为了查找某个节点，以进行其他操作。需要别注意的是单链表必须 要找到前一个节点才可以，所以遍历的终止条件一般都是curr.next == target。高级的方法就是双指针和快慢指针，双指针是指两个指针指向不同的位置，然后以同样的速度向前移动；而快慢指针的特点是一个跑的快（两倍步长到next.next），一个跑的慢（常规步长到next），通常从同一个起点出发，注意它们之间是有区别的。

题目 题解 说明
19. 删除链表的倒数第 N 个结点 题解 双指针
24. 两两交换链表中的节点 题解
25. K 个一组翻转链表 题解
817. 链表组件 题解
面试题 02.02. 返回倒数第 k 个节点 题解
876. 链表的中间结点 题解 快慢指针
1290. 二进制链表转整数 题解
题解
题解


插入和删除

题目 题解 说明
24. 两两交换链表中的节点 题解
82. 删除排序链表中的重复元素 II 题解
83. 删除排序链表中的重复元素 题解
面试题 02.01. 移除重复节点 题解
203. 移除链表元素 题解
237. 删除链表中的节点 题解
题解
题解


链表合并

题目 题解 说明
21. 合并两个有序链表 题解
23. 合并K个升序链表 题解
148. 排序链表 题解 寻找中间点，归并排序
143. 重排链表 题解
1669. 合并两个链表 题解 严格来说不算合并，
主要涉及删除和插入，
以及随机访问
题解


相交链表

属于高级题目，但套路单一，当作基本套路记住就行了。

题目 题解 说明
160. 相交链表 题解
题解
题解


环形链表

主要分两种，一种是链表部分成环；另外就是整个链表就是环（首尾相接），套路也比较单一，记住就行了。

题目 题解 说明
剑指 Offer II 029. 排序的循环链表 题解
141. 环形链表 题解
142. 环形链表 II 题解
题解
题解


综合

| 题目 | 题解 | 说明 | | :– | :– | :– | | 114. 二叉树展开为链表| 题解 | | | 146. LRU 缓存| 题解 | | | 707. 设计链表| 题解 | | | | 题解 | | | | 题解 | |

双向链表

每个节点有两个指针分别指向下一个节点和前一个节点，这是在实际工作中使用的最多的链表形式，绝大部分操作与单链表是一样的，也是线性的。

双向链表因为有两个指针，所以在删除或者插入的时候需要小心处理好四个指针，其他的东西与单链表是一样的。另外，双链表为了达到最好的效果要使用两个哨兵节点，一个是head，指向头节点，一个是tail是末尾节点。

题目 题解 说明
1797. 设计一个验证系统 题解 双向链表，哈希表
LURCache
题解

跳表 SkipList

这是以链表为基础能构造出来的最复杂的数据结构，是二维链表形式，它能够实现log(n)级别的各种操作，效率非常之高，在很多地方替代了平衡二叉树（二叉树只有达到平衡才能到最高的效率，所以工程中使用的二叉树肯定要平衡）。

首先，要明确一下问题，跳表也好，二叉树也好，是解决有序数据集的查询效率的。对于数量为n的数据集来说，如果是无序的肯定是O(n)，但如果数据有序，比如一个排好序的数组或者列表就可以用二分查找，或者用BST（二叉搜索树）时间复杂度都会降低到O(logn)。也就是说跳表解决的问题是有序列数据集的查询问题。

基本原理

前面说了，对于有序数据集，如果是用数组或者列表来存储，查询 效率肯定是O(logn)的，但是连续结构有一个问题就是它的插入和删除是O(n)的。链表呢虽然插入和删除可以做到O(1)，但是它的随机访问（也即查询）慢要O(n)。那么对于一个有序的单链表来说，有没有办法可以提升它的查询效率呢？（插入和删除以及修改都要以查询为先，只有找到了才方便做插删改）。我们要利用数据已排好序，假如能像BST或者二分那样，能把数据集缩小，就可以提升效率。

假如有一个现成的指针指向有序单链表的中间，那么就可以把中单节点的值与目标值比较，如果目标值大于中间节点，那目标值肯定 在后半段，否则就在前半段。假如有更多的中间节点指针，是不是就是二分查找了？可以用空间换时间，给有序单链表建立索引层，每一层也是一个单链表，它会把下面一层链表分成几段，底层是数据集，即有序单链表。这样，从最上层往下层走，就可以把数据集缩小到一个很小的范围内。极端情况下，可以在1/2，1/4，1/8. … 建立索引层，那这是不是就变成BST了？

这就是跳表的核心想。查询的时候总是从最上层开始，因为每一层也是一个有序链表，当下一个节点值大于目标值时，就需要向下走，然后从这一层的这个节点开始，先向后查询，下一个节点大于目标值时，再向下走，这样当前指针就会一层一层的来回跳着走，故名跳表。

实现细节

跳表的原理并不复杂，容易理解，但从原理到编码仍有很多细节需要考虑，比如如何表示每一层？以及分多少层，分层多能提升效率，但分层多占用的空间也越大，而且如果分的过细，不就变成了二叉树了么。以及说在哪些节点建立索引（也即分层），是按固定的位置（1/2, ¼…）还是按什么规律，因为这直接会影响查询效率。

如何实现分层

分层在节点中实现，常规的节点有一个指针next指向下一个节点，在跳表中节点的next指针是一个数组，数组的长度就是这个节点的层数，以此实现分层，0层是底层，level-1是最上层。这样就能实现每层两个方向的遍历方式，每一层的next指针就是这一层的链表，通过curr.next[i]就能向后遍历。下楼（也即从上层往下一层走）就是level-1就下去了。

当然 这里也可以用指针，比如节点有两个指针一个是next，指向同层的后面的节点，以及down，指针下一层的同位置的指针。但并无概念上的区别，总之层的实现是在每个节点上面的。

从大的维度来说，整体仍是一个从左向右的单链表，分层是在每个节点上面的实现的。

在哪里分层

固定位置分层不可取，因为这就是BST的方式啊，数据集的变化可不会因为位置而改变，比如以1/2, 1/4和1/8这几个位置来分层，那假如数据向1/4后的位置集中了，这就会不平衡，就必须做平衡，会比较麻烦（这也是各种平衡二叉树的痛点）。

跳表用一个比较骚的方式，随机化分层，一个长度为n的有序单链表，每个节点都有机会建立分层索引，这样摊还分析后，整体的效率是最好的。

同时，为了防止分层过于集中，还设立了最大层限制MAX_DEPTH。具体的策略是预先设置一个阈值P（0 < P < 1)，每次随机生成一个0~1的浮点数，如果它大于P，那么这个节点的层数加1，否则就返回当前层数（即保持层数不变）。

1
2
3
4
5
6
7

private int randomLevel() {
    int lv = 1;
    while (random.nextDouble() < P_FACTOR && lv < MAX_LEVEL) {
        lv++;
    }
    return lv;
}

哨兵节点

为了方便，可以加入哨兵节点head，head犹为重要，这是整个数据结构的入口，并且有了head后插入和删除的逻辑都能得到简化。

标准实现

为了简单，节点值用整数，节点值的有效范围可以设定为0~n-1，长度共是n。

节点

节点，与单链表很像，一个代表值的int，以及一个数组，代表next指针。

需要注意，一个节点的层数在创建节点时就确定了，在节点的生命周期过程中其层数不会变化。因为对跳表数据结构产生变化 的操作只有插入和删除，插入是生成新的节点，插入时层数已确定；删除是把节点移除，自然也没必要再去改变节点本身了。所以节点的数据类型是Immutable的。

1
2
3
4
5
6
7
8
9

private static final class Node {
    final int value;
    final Node[] next;

    Node(int value, int level) {
        this.value = value;
        next = new Node[level];
    }
}

构造

跳表其实就是一个单链表表，所以整体数据结构也不复杂，一个哨兵入口的头节点head，还有当前节点中的最大层数level，和两个阈值P_FACTOR是要不要增加层深的阈值以及最大层数MAX_LEVEL。

1
2
3
4
5
6
7
8
9
10
11
12

private static final int INF = 1000;
private static final int MAX_LEVEL = 32;
private static final double P_FACTOR = 0.25;
private final Node head;
private int level;
private final Random random;

public SkipList() {
    head = new Node(-INF, MAX_LEVEL);
    level = 0;
    random = new Random();
}

查询

从头节点入口，从其最高层开始查询，具体查询过程与单链表是一样的，持有当前指针，当前指针初化为head节点，不断向后遍历curr直到curr.next[level].val大于目标值，然后走到下一层，继续向后遍历。直到最底层，如果curr.next[0].val等于目标值则找到，否则就是没有，不存在。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public boolean search(int target) {
    Node curr = head;
    for (int i = level - 1; i >= 0; i--) {
        while (curr.next[i] != null && curr.next[i].value < target) {
            curr = curr.next[i];
        }
    }

    if (curr.next[0] != null && curr.next[0].value == target) {
        return true;
    }

    return false;
}

删除

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

public boolean delete(int target) {
    Node[] updates = new Node[MAX_LEVEL];

    Node curr = head;
    for (int i = level - 1; i >= 0; i--) {
        while (curr.next[i] != null && curr.next[i].value < target) {
            curr = curr.next[i];
        }
        updates[i] = curr;
    }
    curr = curr.next[0];
    if (curr == null || curr.value != target) {
        // target not exist
        return false;
    }

    for (int i = 0; i < level; i++) {
        if (updates[i].next[i] != curr) {
            break;
        }
        updates[i].next[i] = curr.next[i];
    }
    while (level > 1 && head.next[level - 1] == null) {
        level--;
    }
    return true;
}

插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

public void insert(int value) {
    Node[] updates = new Node[MAX_LEVEL];
    Arrays.fill(updates, head);

    Node curr = head;
    for (int i = level - 1; i >= 0; i--) {
        while (curr.next[i] != null && curr.next[i].value < value) {
            curr = curr.next[i];
        }
        updates[i] = curr;
    }

    int lv = randomLevel();
    level = Math.max(level, lv);
    Node newNode = new Node(value, lv);

    for (int i = 0; i < lv; i++) {
        newNode.next[i] = updates[i].next[i];
        updates[i].next[i] = newNode;
    }
}

修改

一般的实现中不会不回修改的接口，因为修改就是删除原节点，然后再插入新节点，所以用删除和插入就可以实现了，没必要再添加一个方法。

运行

为了方便加一个调试方法

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
48
49
50
51
52
53
54
55

 public void dump() {
    for (int i = level - 1; i >= 0; i--) {
        StringBuilder sb = new StringBuilder();
        sb.append(String.format("L #%3d [ ", i));
        Node curr = head;
        Node bottomCurr = head;
        while (bottomCurr != null) {
            if (curr != null && curr.value == bottomCurr.value) {
                if (curr == head) {
                    sb.append("-Inf -> ");
                } else {
                    sb.append(String.format("%5d -> ", curr.value));
                }
                curr = curr.next[i];
            } else {
                sb.append("         ");
            }
            bottomCurr = bottomCurr.next[0];
        }
        sb.append(" null ]");
        System.out.println(sb);
    }
}

public static void main(String[] args) {
    SkipList sl = new SkipList();
    int n = 100;
    Random rand = new Random();
    int[] values = new int[7];
    for (int i = 0; i < values.length; i++) {
        values[i] = rand.nextInt(n);
        sl.insert(values[i]);
    }
    System.out.println("After insertion.");
    sl.dump();
    for (int i = 0; i < 3; i++) {
        int target = values[i * 2];
        System.out.println("Searching (true) " + target + " -> " + sl.search(target));
    }
    System.out.println("Delete some.");
    for (int i = 0; i < 3; i++) {
        int target = values[rand.nextInt(n) % values.length];
        System.out.println("Deleting (true) " + target + " -> " + sl.delete(target));
    }
    int target = rand.nextInt(n);
    System.out.println("Deleting " + target + " -> " + sl.delete(target));
    target = rand.nextInt(n);
    System.out.println("Deleting " + target + " -> " + sl.delete(target));
    sl.dump();
    System.out.println("Insert some more.");
    for (int i = 0; i < 4; i++) {
        sl.insert(rand.nextInt(n));
    }
    sl.dump();
}

运行结果，要用等宽字体看才有效果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

After insertion.
L #  3 [ -Inf ->                               29 ->                             null ]
L #  2 [ -Inf ->             16 ->             29 ->                             null ]
L #  1 [ -Inf ->     7 ->    16 ->             29 ->             57 ->           null ]
L #  0 [ -Inf ->     7 ->    16 ->    21 ->    29 ->    44 ->    57 ->    88 ->  null ]
Searching (true) 16 -> true
Searching (true) 29 -> true
Searching (true) 57 -> true
Delete some.
Deleting (true) 16 -> true
Deleting (true) 29 -> true
Deleting (true) 57 -> true
Deleting 75 -> false
Deleting 80 -> false
L #  1 [ -Inf ->     7 ->                             null ]
L #  0 [ -Inf ->     7 ->    21 ->    44 ->    88 ->  null ]
Insert some more.
L #  1 [ -Inf ->     7 ->                      37 ->    41 ->             82 ->           null ]
L #  0 [ -Inf ->     7 ->    17 ->    21 ->    37 ->    41 ->    44 ->    82 ->    88 ->  null ]

完整代码在这里。

相关题目

题目 题解 说明
1206. 设计跳表 题解
题解
题解

参考资料

Comments