引言

链表是最基础也是最重要的数据结构之一,在算法面试中频繁出现。本文将系统讲解链表的原理、实现和经典算法题，帮助你全面掌握链表。

一、链表基础

1.1 什么是链表？

链表是一种线性数据结构，通过指针将一系列节点连接起来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 单链表节点定义
public class ListNode {
    int val;
    ListNode next;
    
    ListNode(int val) {
        this.val = val;
    }
}

// 创建链表: 1 -> 2 -> 3
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);

1.2 数组 vs 链表

特性 数组 链表
内存分配 连续 不连续
随机访问 O(1) O(n)
插入/删除 O(n) O(1)
空间开销 无额外开销 指针开销
缓存友好 是 否

二、单链表实现

2.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
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
public class LinkedList {
    private ListNode head;
    private int size;
    
    // 在头部插入
    public void addFirst(int val) {
        ListNode newNode = new ListNode(val);
        newNode.next = head;
        head = newNode;
        size++;
    }
    
    // 在尾部插入
    public void addLast(int val) {
        ListNode newNode = new ListNode(val);
        if (head == null) {
            head = newNode;
        } else {
            ListNode curr = head;
            while (curr.next != null) {
                curr = curr.next;
            }
            curr.next = newNode;
        }
        size++;
    }
    
    // 在指定位置插入
    public void add(int index, int val) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException();
        }
        
        if (index == 0) {
            addFirst(val);
            return;
        }
        
        ListNode newNode = new ListNode(val);
        ListNode prev = getNode(index - 1);
        newNode.next = prev.next;
        prev.next = newNode;
        size++;
    }
    
    // 删除头节点
    public int removeFirst() {
        if (head == null) {
            throw new NoSuchElementException();
        }
        int val = head.val;
        head = head.next;
        size--;
        return val;
    }
    
    // 删除尾节点
    public int removeLast() {
        if (head == null) {
            throw new NoSuchElementException();
        }
        
        if (head.next == null) {
            int val = head.val;
            head = null;
            size--;
            return val;
        }
        
        ListNode prev = head;
        while (prev.next.next != null) {
            prev = prev.next;
        }
        
        int val = prev.next.val;
        prev.next = null;
        size--;
        return val;
    }
    
    // 删除指定位置节点
    public int remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        
        if (index == 0) {
            return removeFirst();
        }
        
        ListNode prev = getNode(index - 1);
        int val = prev.next.val;
        prev.next = prev.next.next;
        size--;
        return val;
    }
    
    // 获取指定位置节点
    private ListNode getNode(int index) {
        ListNode curr = head;
        for (int i = 0; i < index; i++) {
            curr = curr.next;
        }
        return curr;
    }
    
    // 获取值
    public int get(int index) {
        return getNode(index).val;
    }
    
    // 修改值
    public void set(int index, int val) {
        getNode(index).val = val;
    }
    
    // 查找值
    public int indexOf(int val) {
        ListNode curr = head;
        for (int i = 0; i < size; i++) {
            if (curr.val == val) {
                return i;
            }
            curr = curr.next;
        }
        return -1;
    }
    
    // 打印链表
    public void print() {
        ListNode curr = head;
        while (curr != null) {
            System.out.print(curr.val + " -> ");
            curr = curr.next;
        }
        System.out.println("null");
    }
}

三、双向链表

3.1 双向链表节点

1
2
3
4
5
6
7
8
9
public class DoubleListNode {
    int val;
    DoubleListNode prev;
    DoubleListNode next;
    
    DoubleListNode(int val) {
        this.val = val;
    }
}

3.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
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
public class DoublyLinkedList {
    private DoubleListNode head;
    private DoubleListNode tail;
    private int size;
    
    // 在头部插入
    public void addFirst(int val) {
        DoubleListNode newNode = new DoubleListNode(val);
        if (head == null) {
            head = tail = newNode;
        } else {
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
        }
        size++;
    }
    
    // 在尾部插入
    public void addLast(int val) {
        DoubleListNode newNode = new DoubleListNode(val);
        if (tail == null) {
            head = tail = newNode;
        } else {
            tail.next = newNode;
            newNode.prev = tail;
            tail = newNode;
        }
        size++;
    }
    
    // 删除头节点
    public int removeFirst() {
        if (head == null) {
            throw new NoSuchElementException();
        }
        
        int val = head.val;
        if (head == tail) {
            head = tail = null;
        } else {
            head = head.next;
            head.prev = null;
        }
        size--;
        return val;
    }
    
    // 删除尾节点
    public int removeLast() {
        if (tail == null) {
            throw new NoSuchElementException();
        }
        
        int val = tail.val;
        if (head == tail) {
            head = tail = null;
        } else {
            tail = tail.prev;
            tail.next = null;
        }
        size--;
        return val;
    }
}

四、经典链表算法

4.1 反转链表（LeetCode 206）

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 ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    
    return prev;
}

// 递归法
public ListNode reverseListRecursive(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    
    ListNode newHead = reverseListRecursive(head.next);
    head.next.next = head;
    head.next = null;
    
    return newHead;
}

4.2 检测环（LeetCode 141）

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
// 快慢指针
public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) {
        return false;
    }
    
    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;
}

// 找到环的起点（LeetCode 142）
public ListNode detectCycle(ListNode head) {
    if (head == null || head.next == null) {
        return null;
    }
    
    ListNode slow = head;
    ListNode fast = head;
    
    // 判断是否有环
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        
        if (slow == fast) {
            // 有环，找起点
            ListNode ptr = head;
            while (ptr != slow) {
                ptr = ptr.next;
                slow = slow.next;
            }
            return ptr;
        }
    }
    
    return null;
}

4.3 合并两个有序链表（LeetCode 21）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;
    
    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            curr.next = l1;
            l1 = l1.next;
        } else {
            curr.next = l2;
            l2 = l2.next;
        }
        curr = curr.next;
    }
    
    curr.next = (l1 != null) ? l1 : l2;
    
    return dummy.next;
}

4.4 删除倒数第N个节点（LeetCode 19）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    
    ListNode fast = dummy;
    ListNode slow = dummy;
    
    // fast先走n+1步
    for (int i = 0; i <= n; i++) {
        fast = fast.next;
    }
    
    // 同时移动
    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }
    
    // 删除节点
    slow.next = slow.next.next;
    
    return dummy.next;
}

4.5 找到中间节点（LeetCode 876）

1
2
3
4
5
6
7
8
9
10
11
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;
}

4.6 判断回文链表（LeetCode 234）

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
public boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null) {
        return true;
    }
    
    // 1. 找到中点
    ListNode slow = head;
    ListNode fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    // 2. 反转后半部分
    ListNode secondHalf = reverseList(slow.next);
    
    // 3. 比较
    ListNode p1 = head;
    ListNode p2 = secondHalf;
    boolean result = true;
    
    while (p2 != null) {
        if (p1.val != p2.val) {
            result = false;
            break;
        }
        p1 = p1.next;
        p2 = p2.next;
    }
    
    // 4. 恢复链表（可选）
    slow.next = reverseList(secondHalf);
    
    return result;
}

4.7 相交链表（LeetCode 160）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) {
        return null;
    }
    
    ListNode pA = headA;
    ListNode pB = headB;
    
    // 遍历两个链表，相遇点即为交点
    while (pA != pB) {
        pA = (pA == null) ? headB : pA.next;
        pB = (pB == null) ? headA : pB.next;
    }
    
    return pA;
}

4.8 排序链表（LeetCode 148）

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
// 归并排序
public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    
    // 1. 找到中点
    ListNode mid = getMid(head);
    ListNode right = mid.next;
    mid.next = null;
    
    // 2. 递归排序
    ListNode left = sortList(head);
    right = sortList(right);
    
    // 3. 合并
    return merge(left, right);
}

private ListNode getMid(ListNode head) {
    ListNode slow = head;
    ListNode fast = head.next;
    
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    return slow;
}

private ListNode merge(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;
    
    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            curr.next = l1;
            l1 = l1.next;
        } else {
            curr.next = l2;
            l2 = l2.next;
        }
        curr = curr.next;
    }
    
    curr.next = (l1 != null) ? l1 : l2;
    return dummy.next;
}

五、进阶技巧

5.1 虚拟头节点（Dummy Node）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 简化边界处理
public ListNode removeElements(ListNode head, int val) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    
    ListNode curr = dummy;
    while (curr.next != null) {
        if (curr.next.val == val) {
            curr.next = curr.next.next;
        } else {
            curr = curr.next;
        }
    }
    
    return dummy.next;
}

5.2 快慢指针

1
2
3
4
5
// 应用场景：
// 1. 找中点
// 2. 检测环
// 3. 找倒数第K个节点
// 4. 判断回文

5.3 递归

1
2
3
4
5
6
7
8
9
10
11
12
// 递归反转链表
public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    
    ListNode newHead = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    
    return newHead;
}

六、复杂度分析

操作 数组 单链表 双向链表
访问 O(1) O(n) O(n)
头部插入 O(n) O(1) O(1)
尾部插入 O(1) O(n) O(1)
头部删除 O(n) O(1) O(1)
尾部删除 O(1) O(n) O(1)
中间插入 O(n) O(1)* O(1)*
中间删除 O(n) O(1)* O(1)*

*需要先找到位置，实际为O(n)

七、常见陷阱

7.1 空指针

1
2
3
4
// 始终检查null
if (head == null || head.next == null) {
    return head;
}

7.2 环形链表

1
2
3
4
// 修改链表结构前先检测环
if (hasCycle(head)) {
    // 特殊处理
}

7.3 内存泄漏

1
2
3
4
// 删除节点后清空引用
ListNode toDelete = curr.next;
curr.next = toDelete.next;
toDelete.next = null; // 帮助GC

总结

链表核心要点：

  1. 基本操作：插入、删除、遍历
  2. 经典算法：反转、环检测、合并、排序
  3. 常用技巧：虚拟头、快慢指针、递归
  4. 注意事项：空指针、边界条件、环形链表

参考资料