0x00 链表

在Wikipedia上对链表的定义是一个线性的存储数据的结合。

链表中每一个用于存储数据的单元叫做element或者node，每一个结点中都包含一个指向下一个结点的指针一般被称为next link或者next pointer，剩余的元素一般为数据元素，一般被称为data, information, value, cargo或者payload。链表的第一个元素被称为链表的head。

在某些链表的实现方法中，一般会在链表真正记录数据的结点之前或尾部加入一个多余的结点，通常用来简化或者加速某些链表的算法（list-handling algorithms）或者用于确保链表可以被安全地取消引用（safely dereferenced）以及确保链表始终具有第一个或者最后一个结点，这个结点往往被称为哨兵结点（Sentinel nodes）。

链表一般分为如下几种：

  • 单向链表（Singly linked list）
    单向链表中的结点往往含有数据元素以及一个指向下一个链表结点的指针

  • 双向链表（Doubly linked list）
    双向链表中的结点往往含有数据元素以及一个指向下一个链表结点的指针（next或forwards）以及一个指向上一个链表结点的指针（previous或backwards），使其可以自由的前后移动。
    很多现代操作系统使用双向链表来维护活跃进程、线程以及其他动态对象的引用。很多Rootkit软件就是通过将自己与这些链表解除链接以躲过检测。

    Rootkit一般是指那些用来隐藏其他程序进程的软件。一般都是恶意软件，说白了比如隐藏自己让你无法在任务管理器中找到相关的进程信息。

  • 多向链表（Multiply linked list）
    在一个多向链表中，每一个结点都可能包含2个或多个指针字段用于指向某一特定的数据集，例如想象一个用于存放个人信息的链表，其中有1个指针用于指向链表的下一个结点，还有一个指针指向一个const char *类型的name字段。这个链表即为多向链表。

  • 循环链表（Circular linked list）
    循环链表就是链表的最后一个结点的next指针知道当前链表的第一个结点，形成一个闭合的环的结构。通常情况下链表的next指针一般指向NULL值，用来指示当前结点已经没有下一个可用的结点了。

主要涉及算法：

  • 链表的插入及删除
  • 正向逆向遍历单向链表
  • 按值查找与按位查找

下面介绍一种不常用的链表：

  • 静态链表：静态链表是指借助数组来描述的线性表的链式存储结构，代码如下：

    1
    2
    3
    4
    5
    struct ListNode 
    {
        int data; // 数据域
        int next; // 下一个元素的数组下标
    };

    这种链表一般用于在不支持指针的高级语言上，用数组来模拟单链表，使用起来不如单链表灵活。静态链表的插入、删除操作与普通的链表类似，不需要修改指针，也不需要移动元素，而且可一次性分配较大空间。

0x01 单向链表相关算法及其实现

0x00 插入、删除、查找

有关单项链表的基本操作，插入、删除、获取其中某个位置的元素，可以参考LeetCode题目707. Design Linked List，此题要求你设计一个单项链表，以完成以下操作：

  • get(index): 获取某一特定位置的元素
  • addAtHead(val): 在链表头部添加元素
  • addAtTail(val): 在链表尾部添加元素
  • addAtIndex(index, val): 在下标为index的元素之前添加一个元素
  • deleteAtIndex(index): 删除下标为index的元素
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
// 提交前注释掉此链表结构，否则LeetCode会报ListNode重定义错误
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class MyLinkedList {

    ListNode *head;
    ListNode *tail;
    int size;
public:
    /** Initialize your data structure here. */
    MyLinkedList() {
        head = new ListNode(0);
        tail = new ListNode(0);
        head->next = tail;
        tail->next = nullptr;
        size = 0;
    }

    /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
    int get(int index) {
        if (index + 1 > size || index < 0)
        {
            return -1;
        }
        ListNode *dummy{ head->next };
        while (index--)
        {
            dummy = dummy->next;
        }
        return dummy->val;
    }

    /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
    void addAtHead(int val) {
        head->val = val;
        ListNode *dummy = new ListNode(0);
        dummy->next = head;
        head = dummy;
        ++size;
    }

    /** Append a node of value val to the last element of the linked list. */
    void addAtTail(int val) {
        tail->val = val;
        ListNode *dummy = new ListNode(0);
        tail->next = dummy;
        tail = dummy;
        ++size;
    }

    /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
    void addAtIndex(int index, int val) {
        if (index == size)
        {
            addAtTail(val);
            return;
        }
        if (index > size || index < 0)
        {
            return;
        }
        ListNode *dummy{ head };
        while (index--)
        {
            dummy = dummy->next;
        }
        ListNode *element = new ListNode(val);
        element->next = dummy->next;
        dummy->next = element;
        ++size;
    }

    /** Delete the index-th node in the linked list, if the index is valid. */
    void deleteAtIndex(int index) {
        if (index + 1 > size || index < 0)
        {
            return;
        }
        ListNode *dummy{ head };
        while (index--)
        {
            dummy = dummy->next;
        }
        ListNode *deleted = dummy->next;
        dummy->next = deleted->next;
        deleted->next = nullptr;
        delete deleted;
        --size;
    }
};

此题如果在设计链表时在头部和尾部均添加一个多余的哨兵结点，会使整个算法的效率提升，以及简化代码量，尤其是在向尾部添加一个元素时，如果不使用哨兵结点，向尾部添加元素时，需要提前遍历至尾部，此过程的时间复杂度为O(N)O(N)，如果使用哨兵结点就可以将时间复杂度缩短到O(1)O(1)。此代码超越99.84%的人，前面唯一一个比它快的代码是使用的vector来作的弊。

单链表的删除，从一道LeetCode题目看起Remove Linked List Elements，这道题目要求你删除单链表中与给定数据匹配的数据，代码如下：

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
class Solution {
public:
    ListNode * removeElements(ListNode* head, int val) {
        if (!head)
        {
            return nullptr;
        }
        ListNode *prev{ head }, *current{ head->next };
        while (current)
        {
            if (current->val == val)
            {
                prev->next = current->next;
                delete current;
                current = prev->next;
            }
            else
            {
                prev = current;
                current = current->next;
            }
        }
        if (head->val == val)
        {
            ListNode *dummy{ head->next };
            delete head;
            return dummy;
        }
        return head;
    }
};

上述代码的时间复杂度为O(N)O(N)。

有关单链表设计中的头结点，或者加入在头部的哨兵结点的好处：

  • 开始结点（也就是真正存放数据的那个结点）的位置在头结点的指针域中，所以在链表第一个位置上的操作和其他位置上的操作一直，无需进行特殊处理。以方便运算的实现。
  • 只需以头结点的next指针域是否为空来判断当前链表是否为空，这样可以统一空表与非空表的处理。

0x01 逆置单链表

逆置单链表的问题，无需改变的链表的结构，O(N)O(N)的时间复杂度即可完成，对于LeetCode题目206. Reverse Linked List，我一开始给出了如下代码，O(N)O(N)的时间复杂度再加上O(N)O(N)的空间复杂度：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    ListNode * reverseList(ListNode* head) {
        std::vector<int> nums;
        for (ListNode *p = head; p != NULL; p = p->next)
        {
            nums.emplace_back(p->val);
        }
        int count = nums.size();
        for (ListNode *p = head; p != NULL; p = p->next)
        {
            p->val = nums[--count];
        }
        return head;
    }
};

但是看了别人的提交记录之后，发现有人用一趟while循环外加O(1)O(1)的空间复杂度就把问题解决了，它的思路就是改变链表的物理结构，让链表从结构上整体翻转，而不是像我那样只改变里面的数字不改变物理结构，学会了它的思路后，自己动手写了一个，耗时4ms击败100%的人，O(N)O(N)的时间复杂度以及O(1)O(1)的额外空间占用代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    ListNode * reverseList(ListNode* head) {
        if (!head || !head->next)
        {
            return head;
        }
        ListNode *prev{ nullptr },
            *current{ head },
            *next{ current->next };
        while (next)
        {
            current->next = prev;
            prev = current;
            current = next;
            next = current->next;
        }
        current->next = prev;
        return current;
    }
};

题目逆置单链表加强版Reverse Linked List II，题目提示Do it in one-pass.也就是使用一趟循环实现，代码如下，O(N)O(N)的时间复杂度以及O(1)O(1)的空间复杂度：

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
class Solution {
public:
    ListNode * reverseBetween(ListNode* head, int m, int n) {
        ListNode *prev{}, *current{}, *next{},
            *dummy{ head }, *left{};
        for (int i = 1; i <= n; ++i)
        {
            if (i > m)
            {
                current->next = prev;
                prev = current;
                current = next;
                next = current->next;
            }
            else if (i == m)
            {
                current = dummy;
                next = current->next;
            }
            else
            {
                left = dummy;
                dummy = dummy->next;
            }
        }
        current->next = prev;
        dummy->next = next;
        if (left)
        {
            left->next = current;
        }
        if (m == 1)
        {
            return current;
        }
        return head;
    }
};

因为每次循环都要进行if-else if-else判断结构，导致代码的整体效率偏低，我又撰写了另一个版本，

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    ListNode * reverseBetween(ListNode* head, int m, int n) {
        int size{ n - m + 1 };
        int *nums = new int[size];
        ListNode *dummy{ head }, *begin{};
        for (int i = 1; i < m; ++i, dummy = dummy->next);
        begin = dummy;
        for (int i = 0; i < size; nums[i] = dummy->val, dummy = dummy->next, ++i);
        for (int i = n - m; i >= 0; begin->val = nums[i], begin = begin->next, --i);
        return head;
    }
};

设需要逆置的区间为[M,N][M,N]则，算法的时间复杂度为O(2N−M+2)O(2N-M+2)

0x02 奇靠前偶靠后

这个是来源于一道LeetCode题目328. Odd Even Linked List，此题要求你将下标为偶数的元素全部移动到链表的最后，而且要在源链表的物理结构上实现（in place），我的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    ListNode * oddEvenList(ListNode* head) {
        if (!head || !head->next)
        {
            return head;
        }
        ListNode *dummyHead{ head }, *even{ new ListNode(0) };
        ListNode *dummyHeadPrev{}, *dummyEven{ even };
        while (dummyHead && dummyHead->next)
        {
            dummyEven->next = dummyHead->next;
            dummyEven = dummyEven->next;
            dummyHead->next = dummyHead->next->next;
            dummyHeadPrev = dummyHead;
            dummyHead = dummyHead->next;
        }
        dummyEven->next = nullptr;
        ListNode **tail{ dummyHead ? &dummyHead : &dummyHeadPrev };
        (*tail)->next = even->next;
        return head;
    }
};

运行时间8ms超过100%的人，时间复杂度为O(N2)O(\frac{N}{2})，while循环两个两个跳着走就可以，空间复杂度为O(1)O(1)。

0x03 单向链表的中点

从一道LeetCode题目说起，876. Middle of the Linked List，此题给定一个单向链表，要你寻找当前链表中点位置的元素，当链表长度为NN时此题可以在N2\frac{N}{2}的时间复杂度以及O(1)O(1)的空间复杂度内完成，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    ListNode * middleNode(ListNode* head) {
        ListNode *slow{ head }, *fast{ head };
        while (slow && fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};

0x04 移除排序后单链表中的重复元素

此为一道LeetCode题目，83. Remove Duplicates from Sorted List，此题给定一个排序过的单项链表，要求你移除其中的重复元素，一开始写出了如下代码，运行时间8ms，击败了98.02%的人：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    ListNode * deleteDuplicates(ListNode* head) {
        ListNode *dummy{ head };
        while (dummy && dummy->next)
        {
            if (dummy->val == dummy->next->val)
            {
                ListNode *dummy2{ dummy->next }, *deleted{ dummy->next };
                while (dummy2 && dummy2->next && dummy->val == dummy2->next->val)
                {
                    dummy2 = dummy2->next;
                }
                dummy->next = dummy2->next;
                dummy2->next = nullptr;
                delete deleted;
            }
            dummy = dummy->next;
        }
        return head;
    }
};

我们可以用下面的方法来将if里面的那个while循环消除掉，从而大大提升程序的效率，代码如下：

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
class Solution {
public:
    ListNode * deleteDuplicates(ListNode* head) {
        if (!head || !head->next)
        {
            return head;
        }
        ListNode *current{ head }, *next{ head->next };
        while (next)
        {
            if (current->val == next->val)
            {
                current->next = next->next;
                delete next;
                next = current->next;
            }
            else
            {
                current = next;
                next = next->next;
            }
        }
        return head;
    }
};

理论上来讲上述两种算法的时间复杂度均为O(N)O(N)。

0x05 查找交叉结点

此仍为一道LeetCode题目，160. Intersection of Two Linked Lists，此题要求你查找两个单向链表中处于同一交叉点的元素，也就是指向同一内存空间的元素，示例：

1
2
3
4
5
A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

代码如下：

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
class Solution {

    ListNode *getIntersection(ListNode *headA, int lenA, ListNode *headB, int lenB)
    {
        if (lenB < lenA)
        {
            return getIntersection(headB, lenB, headA, lenA);
        }
        while (lenB-- != lenA)
        {
            headB = headB->next;
        }
        while (headA != headB)
        {
            headA = headA->next;
            headB = headB->next;
        }
        return headA;
    }
public:
    ListNode * getIntersectionNode(ListNode *headA, ListNode *headB) {
        int lenA{}, lenB{};
        ListNode *dummy{ headA };
        while(dummy)
        {
            dummy = dummy->next;
            ++lenA;
        }
        dummy = headB;
        while (dummy)
        {
            dummy = dummy->next;
            ++lenB;
        }
        if (!lenA || !lenB)
        {
            return nullptr;
        }
        return getIntersection(headA, lenA, headB, lenB);
    }
};

按照题目要求此代码时间复杂度为O(N)O(N)且空间复杂度为O(1)O(1)。

其提交代码中，最快的代码可以将算法消减到一趟循环实现，代码如下：

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
class Solution {
public:
    ListNode * getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == nullptr || headB == nullptr) return nullptr;
        ListNode* pA = headA;
        ListNode* pB = headB;
        ListNode* prevA = nullptr;
        ListNode* prevB = nullptr;
        while (pA != pB) {
            if (pA->next == nullptr) {
                prevA = pA;
                pA = headB;
            }
            else {
                pA = pA->next;
            }
            if (pB->next == nullptr) {
                prevB = pB;
                pB = headA;
            }
            else {
                pB = pB->next;
            }
            if (prevA != nullptr && prevB != nullptr &&
                prevA != prevB)
            {
                return nullptr;
            }
        }
        return pA;
    }
};

0x06 删除单链表中从结尾开始数的第N号元素

同样，来自一道LeetCode题目，19. Remove Nth Node From End of List，给定一个单链表和一个整数N，删除从结尾算起的第N号元素，对于此题采用递归的方法来倒序遍历链表以找到从结尾算起的第N号元素之前的那一个，然后将其next删除即可，算法不难想，时间复杂度在O(N)O(N)，运行效率超过100%的人，代码如下：

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
class Solution {
    int m, n;

    void reverseTravel(ListNode *head)
    {
        if (head)
        {
            ++m;
            reverseTravel(head->next);
        }
        if (!--n)
        {
            ListNode *dummy{ head->next };
            head->next = dummy->next;
            delete dummy;
        }
    }
public:
    ListNode * removeNthFromEnd(ListNode* head, int n) {
        this->n = n + 2;
        this->m = 0;
        reverseTravel(head);
        if (m == n)
        {
            ListNode *dummy{ head->next };
            delete head;
            return dummy;
        }
        return head;
    }
};

0x07 两两交换单链表中的元素

这个是一道LeetCode题目，24. Swap Nodes in Pairs，题目中提出了一个较为奇葩的需求就是两两交换单向链表中的元素，例如给定单链表1->2->3->4，则返回2->1->4->3，一趟循环O(N)O(N)的复杂度即可实现，代码如下：

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
class Solution {

    void swap(ListNode *prev, ListNode *current, ListNode *next)
    {
        current->next = next->next;
        next->next = current;
        prev->next = next;
    }
public:
    ListNode * swapPairs(ListNode* head) {
        if (!head || !head->next)
        {
            return head;
        }
        ListNode *current{ head }, *next{ head->next };
        current->next = next->next;
        next->next = current;
        head = next;
        while (current && current->next && current->next->next)
        {
            swap(current, current->next, current->next->next);
            current = current->next->next;
        }
        return head;
    }
};

0x02 双向链表相关算法及其实现

双向链表就是在单向链表的基础上，对每一个结点都添加一个指向上一个元素的指针所构成的链表。双向链表唯一的好处就是其遍历指针可以随意向前向后调转方向。双向链表并不会降低单项链表在遍历时的时间复杂度O(N)O(N)，只是多了一种中途调转方向的机会。

0x00 插入、删除、查找

还是设计单链表的那个LeetCode题目，707. Design Linked List，这次我们用双向链表来实现一下，代码如下：

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
class MyLinkedList {

    struct LNode
    {
        int data;
        LNode *next;
        LNode *prev;
        LNode(int d) :data(d), next(nullptr), prev(nullptr) {}
    };

    LNode *head;
    LNode *tail;
    int size;
public:
    /** Initialize your data structure here. */
    MyLinkedList() {
        size = 0;
        head = new LNode(0);
        tail = new LNode(0);
        head->next = tail;
        tail->prev = head;
    }

    /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
    int get(int index) {
        if (index < 0 || index >= size)
        {
            return -1;
        }
        LNode *dummy = head->next;
        while (index--)
        {
            dummy = dummy->next;
        }
        return dummy->data;
    }

    /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
    void addAtHead(int val) {
        head->data = val;
        LNode *dummy = new LNode(0);
        dummy->next = head;
        head->prev = dummy;
        head = dummy;
        ++size;
    }

    /** Append a node of value val to the last element of the linked list. */
    void addAtTail(int val) {
        tail->data = val;
        LNode *dummy = new LNode(0);
        dummy->prev = tail;
        tail->next = dummy;
        tail = dummy;
        ++size;
    }

    /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
    void addAtIndex(int index, int val) {
        if (index > size || index < 0)
        {
            return;
        }
        if (index == size)
        {
            addAtTail(val);
            return;
        }
        LNode *dummy = head;
        while (index--)
        {
            dummy = dummy->next;
        }
        LNode *inserted = new LNode(val);
        inserted->prev = dummy;
        inserted->next = dummy->next;
        dummy->next->prev = inserted;
        dummy->next = inserted;
        ++size;
    }

    /** Delete the index-th node in the linked list, if the index is valid. */
    void deleteAtIndex(int index) {
        if (index >= size || index < 0)
        {
            return;
        }
        LNode *dummy = head;
        while (index--)
        {
            dummy = dummy->next;
        }
        LNode *deleted = dummy->next;
        dummy->next = deleted->next;
        deleted->next->prev = dummy;
        delete deleted;
        --size;
    }
};

在跑过之后，发现建立双向链表操作的时间与建立单项链表操作所花费的时间是相同的，整个题目双向链表和单项链表所花费的时间基本相同，均为16ms，但是建立双向链表可以为以后的复杂操作提供更多的便利性。

0x03 循环链表的基本概念

循环链表与单链表的区别在于其最后一个结点不是指向NULL，而是指向头结点，从而使链表整个地形成一个环状结构，因为整个表中不再有指向NULL的结点，所以循环链表判空的方法为头结点的next指针是否等于头结点。正是因为循环链表的环状结构使得在任何一个结点上的插入和删除操作都是等价的，无需判断插入的结点是否是表头结点和尾结点。并且循环链表可以从任何一个结点开始往后顺序遍历整个链表。

如果对链表常做的操作为在表头和表尾进行，可以使用带尾指针的循环链表，从而使效率更高，其原因为如果仅设头指针的话，对表尾的操作需要O(N)O(N)的时间复杂度（先找到表尾），如果设的为尾指针，则尾指针的下一个即为头指针，对表头和表尾的操作仅需要O(1)O(1)的复杂度。