【数据结构与算法】系列三 - 链表

发表于 | 分类于 ，
| 字数统计 3k 字 | 阅读时长 13 分钟

动态数组有个明显的缺点：如果动态申请倍数内存，可能会造成内存空间的大量浪费（比如只需要20个内存，但申请了30个。如果根据数量申请指定个数，又会造成效率降低）。

能否用到多少就申请多少内存？链表可以办到这一点。

一、链表

链表（Linked List）是一种链式存储的线性表，所有元素的内存地址不一定是连续的。

数组是连续存储的线性表，内存地址是连续的。

先申请一个节点内存，然后把元素放到节点中，节点的内存中存放着指向下一个节点的内存地址。第一个节点叫头节点，最后一个节点叫尾节点（尾节点指向的下一个节点地址是空的）。

1.1. 链表的设计

创建一个链表对象，对象包含链表大小和指向头节点的地址。然后创建其他节点，并通过节点地址依次链接，尾节点的下一个节点地址指向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
public class LinkedList<E> {
    /**
     * 节点的数量
     */
    private int size;
    /**
     * 头节点
     */
    private Node<E> first;

    private static class Node<E> {
        /**
         * 节点存放的元素
         */
        E element;
        /**
         * 指向的下一个节点
         */
        Node<E> next;

        public Node(E element, Node<E> next) {
            this.element = element;
            this.next = next;
        }
    }
}

1.2. 接口设计

链表的大部分接口和动态数组是一致的。但是大部分接口的内部实现肯定是不一样的，可以通过接口（interface）声明公共方法，把公共代码部分放在抽象类中（abstract），抽象类实现定义的接口。这样子类（数组、链表）只需继承抽象类并实现自己的业务代码即可。

1.2.1. 清空元素

清空元素只需要设置size = 0; first = null。只要第一个节点没有对象强引用就会被释放，依次类推，所有节点都会被释放。

1
2
3
4
public void clear() {
    size = 0;
    first = null;
}

1.2.2. 添加元素

如果要在索引为1的位置添加一个元素，需要索引为0的元素指向要添加的元素，添加的元素指向原来索引为2的元素。

添加前：

添加后：

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 void add(int index, E element) {
    if (index == 0) {
        first = new Node<>(element, first);
    } else {
        Node<E> prev = node(index - 1);
        prev.next = new Node<>(element, prev.next);
    }
    
    size++;
}

// 获取index位置对应的节点对象
private Node<E> node(int index) {    
    if (index < (size >> 1)) {
        Node<E> node = first;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    } else {
        Node<E> node = last;
        for (int i = size - 1; i > index; i--) {
            node = node.prev;
        }
        return node;
    }
}

在编写链表过程中，要注意边界测试，比如index为0，size-1、size。

1.2.3. 删除元素

删除和添加有点类似，都是需要拿到前一个元素的指向。把前一个元素的指向换成下一个指向（prev.next.next）。

例如，删除索引1的元素，需要把索引0的元素指向换成指向索引2：

1
2
3
4
5
6
7
8
9
10
11
12
13
public E remove(int index) {
    Node<E> node;
    if (index == 0) {
        node = first;
        first = first.next;
    } else {
        Node<E> prev = node(index - 1);
        node = prev.next;
        prev.next = node.next;
    }
    size--;
    return node.element;
}

1.2.4. 元素找索引

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int indexOf(E element) {
    if (element == null) {
        Node<E> node = first;
        for (int i = 0; i < size; i++) {
            if (node.element == null) return i;
            node = node.next;
        }
    } else {
        Node<E> node = first;
        for (int i = 0; i < size; i++) {
            if (element.equals(node.element)) return i;
            node = node.next;
        }
    }
}

1.2.5. 完整代码

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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
package com.mj;

import com.mj.AbstractList;

public class LinkedList<E> extends AbstractList<E> {
    private Node<E> first;
    private Node<E> last;

    private static class Node<E> {
        E element;
        Node<E> prev;
        Node<E> next;
        public Node(Node<E> prev, E element, Node<E> next) {
            this.prev = prev;
            this.element = element;
            this.next = next;
        }
        
        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            
            if (prev != null) {
                sb.append(prev.element);
            } else {
                sb.append("null");
            }
            
            sb.append("_").append(element).append("_");

            if (next != null) {
                sb.append(next.element);
            } else {
                sb.append("null");
            }
            
            return sb.toString();
        }
    }

    @Override
    public void clear() {
        size = 0;
        first = null;
        last = null;
    }

    @Override
    public E get(int index) {
        return node(index).element;
    }

    @Override
    public E set(int index, E element) {
        Node<E> node = node(index);
        E old = node.element;
        node.element = element;
        return old;
    }

    @Override
    public void add(int index, E element) {
        rangeCheckForAdd(index);

        if (index == size) { // 往最后面添加元素
            Node<E> oldLast = last;
            last = new Node<>(oldLast, element, null);
            if (oldLast == null) { // 这是链表添加的第一个元素
                first = last;
            } else {
                oldLast.next = last;
            }
        } else {
            Node<E> next = node(index); 
            Node<E> prev = next.prev; 
            Node<E> node = new Node<>(prev, element, next);
            next.prev = node;
            
            if (prev == null) { // index == 0
                first = node;
            } else {
                prev.next = node;
            }
        }
        
        size++;
    }

    @Override
    public E remove(int index) {
        rangeCheck(index);

        Node<E> node = node(index);
        Node<E> prev = node.prev;
        Node<E> next = node.next;
        
        if (prev == null) { // index == 0
            first = next;
        } else {
            prev.next = next;
        }
        
        if (next == null) { // index == size - 1
            last = prev;
        } else {
            next.prev = prev;
        }
        
        size--;
        return node.element;
    }

    @Override
    public int indexOf(E element) {
        if (element == null) {
            Node<E> node = first;
            for (int i = 0; i < size; i++) {
                if (node.element == null) return i;
                
                node = node.next;
            }
        } else {
            Node<E> node = first;
            for (int i = 0; i < size; i++) {
                if (element.equals(node.element)) return i;
                
                node = node.next;
            }
        }
        return ELEMENT_NOT_FOUND;
    }

    /**
     * 获取index位置对应的节点对象
     * @param index
     * @return
     */
    private Node<E> node(int index) {
        rangeCheck(index);
        
        if (index < (size >> 1)) {
            Node<E> node = first;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
            return node;
        } else {
            Node<E> node = last;
            for (int i = size - 1; i > index; i--) {
                node = node.prev;
            }
            return node;
        }
    }

    @Override
    public String toString() {
        StringBuilder string = new StringBuilder();
        string.append("size=").append(size).append(", [");
        Node<E> node = first;
        for (int i = 0; i < size; i++) {
            if (i != 0) {
                string.append(", ");
            }
            
            string.append(node);
            
            node = node.next;
        }
        string.append("]");
        return string.toString();
    }
}

二、练习

2.1. 删除链表中的节点

LeetCode：https://leetcode-cn.com/problems/delete-node-in-a-linked-list/

题目：

题解：

2.2. 反转链表

LeetCode：https://leetcode-cn.com/problems/reverse-linked-list/

2.2.1. 双指针迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public ListNode reverseList(ListNode head) {
        //申请节点，pre和 cur，pre指向null
        ListNode pre = null;
        ListNode cur = head;
        ListNode tmp = null;
        while(cur!=null) {
            //记录当前节点的下一个节点
            tmp = cur.next;
            //然后将当前节点指向pre
            cur.next = pre;
            //pre和cur节点都前进一位
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
}

我们可以申请两个指针：第一个指针叫pre，最初是指向null的。第二个指针cur指向hea，然后不断遍历cur。每次迭代到cur，都将cur的next指向pre，然后pre和cur前进一位。都迭代完了(cur变成null了)，pre就是最后一个节点了。

注意：tmp变量是为了保证节点不会被释放。

动画演示：https://blog.idbeny.com/yy3yf.mp4

2.2.2. 递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public ListNode reverseList(ListNode head) {
        //递归终止条件是当前为空，或者下一个节点为空
        if(head==null || head.next==null) {
            return head;
        }
        //这里的cur就是最后一个节点
        ListNode cur = reverseList(head.next);
        //这里请配合动画演示理解
        //如果链表是 1->2->3->4->5，那么此时的cur就是5
        //而head是4，head的下一个是5，下下一个是空
        //所以head.next.next 就是5->4
        head.next.next = head;
        //防止链表循环，需要将head.next设置为空
        head.next = null;
        //每层递归函数都返回cur，也就是最后一个节点
        return cur;
    }
}

递归的两个条件：

  1. 终止条件是当前节点或者下一个节点==null
  2. 在函数内部，改变节点的指向，也就是head的下一个节点指向head递归函数那句head.next.next = head

递归函数中每次返回的cur其实只最后一个节点，在递归函数内部，改变的是当前节点的指向。

动画演示：https://blog.idbeny.com/tlsrp.mp4@normal

2.3. 环形链表

LeetCode：https://leetcode-cn.com/problems/linked-list-cycle/

题目：


2.3.1. 哈希表

思路及算法:

最容易想到的方法是遍历所有节点，每次遍历到一个节点时，判断该节点此前是否被访问过。

具体地，我们可以使用哈希表来存储所有已经访问过的节点。每次我们到达一个节点，如果该节点已经存在于哈希表中，则说明该链表是环形链表，否则就将该节点加入哈希表中。重复这一过程，直到我们遍历完整个链表即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> seen = new HashSet<ListNode>();
        while (head != null) {
            if (!seen.add(head)) {
                return true;
            }
            head = head.next;
        }
        return false;
    }
}

复杂度分析：

  • 时间复杂度：O(N)，其中N是链表中的节点数。最坏情况下我们需要遍历每个节点一次。

  • 空间复杂度：O(N)，其中N是链表中的节点数。主要为哈希表的开销，最坏情况下我们需要将每个节点插入到哈希表中一次。

2.3.2. 快慢指针

思路及算法:

假想「乌龟」和「兔子」在链表上移动，「兔子」跑得快，「乌龟」跑得慢。当「乌龟」和「兔子」从链表上的同一个节点开始移动时，如果该链表中没有环，那么「兔子」将一直处于「乌龟」的前方；如果该链表中有环，那么「兔子」会先于「乌龟」进入环，并且一直在环内移动。等到「乌龟」进入环时，由于「兔子」的速度快，它一定会在某个时刻与乌龟相遇，即套了「乌龟」若干圈。

我们可以根据上述思路来解决本题。具体地，我们定义两个指针，一快一满。慢指针每次只移动一步，而快指针每次移动两步。初始时，慢指针在位置 head，而快指针在位置 head.next。这样一来，如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表。否则快指针将到达链表尾部，该链表不为环形链表。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }
}

为什么我们要规定初始时慢指针在位置head，快指针在位置head.next，而不是两个指针都在位置head（即与「乌龟」和「兔子」中的叙述相同）？

观察下面的代码，我们使用的是while循环，循环条件先于循环体。由于循环条件一定是判断快慢指针是否重合，如果我们将两个指针初始都置于head，那么while 循环就不会执行。因此，我们可以假想一个在head之前的虚拟节点，慢指针从虚拟节点移动一步到达head，快指针从虚拟节点移动两步到达head.next，这样我们就可以使用while 循环了。

当然，我们也可以使用do-while循环。此时，我们就可以把快慢指针的初始值都置为head。

复杂度分析:

  • 时间复杂度：O(N)，其中N是链表中的节点数。

    • 当链表中不存在环时，快指针将先于慢指针到达链表尾部，链表中每个节点至多被访问两次。

    • 当链表中存在环时，每一轮移动后，快慢指针的距离将减小一。而初始距离为环的长度，因此至多移动N轮。

  • 空间复杂度：O(1)。我们只使用了两个指针的额外空间。

推荐算法动画执行网站：https://visualgo.net/zh