【算法】链表总结

一、前言

链表： 主要包含 数据 和 指针 两部分。

class ListNode {
    int val;       // 数据
    ListNode next; // 指针
    ListNode(int x) { val = x; }
}

按类别可分为 3 种：

• 单链表：最常见的，只有一个指针。
• 双向链表：即有 2 个指针，一个指向前一个，一个指向后一个。
• 循环链表：即链表中有回路。

经常运用到单链表的操作：新增、删除 和 反转

1. 新增： 即在链表中新增一个节点

// 代码如下：
newNode.next = node.next; // 1. 新节点的指针 指向 当前节点的指针方向
node.next = newNode;      // 2. 当前节点的指针 指向 新节点

1. 删除： 即在链表中删除一个节点

// 代码如下：
node.next = deleteNode.next;
deleteNode.next = null;

1. 反转： 指针朝向逆序

// 代码如下：对应 LeetCode 206
// 比如说给你的单链表是：   1 -> 2 -> 3 -> 4 -> 5 -> null
// 你要返回的反转后的链表是：5 -> 4 -> 3 -> 2 -> 1 -> null
public ListNode reverseList(ListNode head) {
    ListNode pre = null;   // 指针pre：指向当前节点的前一个节点
    ListNode curr = head;  // 指针curr：指向当前节点
    while (curr != null) {
        ListNode temp = curr.next; // 记录 next 指向
        curr.next = pre;           // 1. 当前节点的指针 指向 pre节点
        pre = curr;                // 2. pre 指向 当前节点
        curr = temp;               // 3. 当前节点 指向 temp
    }
    return pre;
}

解决环形链表

在链表中使用两个速度不同的指针时会遇到的情况：

• 如果没有环，快指针将停在链表的末尾。
• 如果有环，快指针最终将与慢指针相遇。

假设较快的指针每次移动 2 步，较慢的指针每次移动 1 步。

• 如果没有循环，快指针需要 N/2 次才能到达链表的末尾，其中 N 是链表的长度。
• 如果存在循环，则快指针需要 M 次才能赶上慢指针，其中 M 是列表中循环的长度。

显然，M <= N 。所以将循环运行 N 次。因此，该算法的时间复杂度总共为 O(N)。

二、题目

（1）判断单链表是否有环（易）

LeetCode 141

题干分析

这个题目说的是，给你一个单链表，你要判断它是否会形成环，也就是链表的最后一个节点指向了前面一个已经存在的节点。

思路解法

思路有二：

1. 用 HashSet 记录节点：当有重复节点出现，则为有环。

2. 双指针： 快、慢指针最终是否相遇。

   • 快指针：每次走 2 步
   • 慢指针：每次走 1 步

AC 代码：

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null) return false;
        ListNode fast = head, slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;         // 快指针每次走 2 步
            slow = slow.next;              // 慢指针每次走 1 步
            if (fast == slow) return true; // 最终是否相遇
        }
        return false;
    }
}

（2）单链表中圆环的开始节点（中）

LeetCode 142

题干分析

这个题目说的是，给你一个单链表，你要返回这个链表中，圆环的开始节点。如果单链表无环，就返回空指针。

比如说，给你的单链表是：
​
1 -> 2 -> 4 -> 8 -> 2
// 最后的 2 和前面的 2 是同一个节点
​
这个链表中存在环，并且环的开始节点是 2，于是你要返回节点 2。

思路解法

思路有二：

1. 用 HashSet 记录节点：当有重复节点出现，即首次出现，则为圆环开始节点。

2. 双指针： 快、慢指针首次相遇后，临时指针从开始节点开始每次 1 步，跟慢指针一起走，再次相遇则为圆环的开始节点。

   • 快指针：每次走 2 步
   • 慢指针：每次走 1 步

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) return null;
        ListNode fast = head, slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) { // 1. 首次相遇
                // 2. 从开始节点开始走，再次相遇则为圆环的开始节点
                for (ListNode p = head; p != slow; p = p.next, slow = slow.next);
                return slow;
            }
        }
        return null;
    }
}

（3）奇偶链表调顺序（中）

LeetCode 328. Odd Even Linked List

题干分析

这个题目说的是，给你一个单链表，你要重新排列这个链表，把奇数节点全都放到链表前面，偶数节点全都放到链表后面，并且奇数节点内和偶数节点内的节点相对顺序保持不变。

注意：

• 这里说的奇数和偶数，指的是节点的位置，而不是节点值。
• 并且把头节点看作第一个节点，也就是说头节点是奇数节点。
• 这个题目的时间复杂度要求是 O(n)，空间复杂度要求是 O(1)。

# 比如说，给你的链表是：
0 -> 1 -> 2 -> 4 -> 8
​
# 奇数位置上的节点是：
[0, 2, 8]
​
# 偶数位置上的节点是：
[1, 4]
​
# 因此重新排列后的链表就是：
0 -> 2 -> 8 -> 1 -> 4

思路解法

思路： 3 个指针来表示

• 偶数头指针：指向偶数链第一个，用于之后衔接奇数链
• 偶数指针：在偶数链上移动
• 奇数指针：在奇数链上移动

AC 代码：

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
​
public class LeetCode_328 {
    // Time: O(n), Space: O(1), Faster: 100.00%
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null || head.next.next == null)
            return head;
        ListNode evenHead = head.next;        // 偶数头指针
        ListNode odd = head, even = evenHead; // 奇数指针、偶数指针
        while (even != null && even.next != null) {
            odd.next = even.next;   // 奇数的指针指向偶数的指针
            odd = odd.next;         // 移动
            
            even.next = odd.next;   // 偶数的指针指向奇数的指针
            even = even.next;       // 移动
        }
        odd.next = evenHead;
        return head;
    }
​
}

（4）链表加一（中）

题干分析

这个题目说的是，给你一个不为空的单链表，它表示一个非负整数。链表中的每个节点值都位于 0~9 之间，代表整个非负整数中的一位。你要将这个非负整数加 1，然后返回结果链表。

# 比如说，给你的链表是：
1 -> 2 -> 4
​
# 它表示整数 124，加 1 等于 125，于是你要返回链表：
1 -> 2 -> 5

思路解法

此题麻烦点在于： +1 后，数值会进位。

容易想到的解法： 暴力法，链表转换 -> 数值 转换回 -> 链表。（解法略。）

这里考虑如何在原链表进行 +1 操作。

有两个特例：

1. 栗子一：1 -> 2 -> 9 -> 9，+1 后，1 -> 3 -> 0 -> 0
2. 栗子二：9 -> 9 -> 9 ，+1 后，1 -> 0 -> 0 -> 0，会有额外头节点

综上，思路步骤分为：

1. 额外头节点： 往链表头部插入一个节点，预防进位问题。
2. 找到最后一个数值不是 9 的节点 notNine。
3. notNine 数值 + 1
4. notNine节点之后的节点，数值均赋值为 0。（因为进位了）
5. 判断需不需要额外头节点

AC 代码：

// Time: O(n), Space: O(1)
public ListNode plusOne(ListNode head) {
    ListNode maybe = new ListNode(0), notNine = maybe;
    maybe.next = head;
    // 1. 找到最后一个不是 9 的节点：notNine
    for (ListNode p = head; p != null; p = p.next) {
        if (p.val != 9)
            notNine = p;
    }
    // 2. notNine 的数值 +1
    notNine.val += 1;
    // 3. notNine 之后的节点的数值均赋值为 0
    for (ListNode p = notNine.next; p != null; p = p.next) {
        p.val = 0;
    }
    // 4. 判断需不需要额外头节点
    if (notNine == maybe) return maybe;
    else return head;
}

（5）单链表排序（中）

题干分析

这个题目说的是，给你一个单链表，你要写一个函数，对它进行排序，然后返回排序后的链表。

# 比如说，给你的单链表是：
4 -> 8 -> 2 -> 1
​
# 你要返回排序后的链表：
1 -> 2 -> 4 -> 8

思路解法

解法有二： 类似快排 和 类似归并排序。

1. 方法一：类似快排

AC代码：

// Time: O(n*log(n)), Space: O(n), Faster: 6.60%
public ListNode quickSortList(ListNode head) {
    quickSort(head, null);
    return head;
}
​
private void quickSort(ListNode head, ListNode end) {
    if (head == end || head.next == end) return;
    int pivot = head.val;
    ListNode slow = head, fast = head.next;
    while (fast != end) {
        if (fast.val <= pivot) {
            slow = slow.next;
            swap(slow, fast);
        }
        fast = fast.next;
    }
    swap(head, slow);
    quickSort(head, slow);
    quickSort(slow.next, end);
}
​
private void swap(ListNode a, ListNode b) {
    int tmp = a.val;
    a.val = b.val;
    b.val = tmp;
}

1. 方法二：类似归并排序

AC 代码：

// Time: O(n*log(n)), Space: O(log(n)), Faster: 97.67%
public ListNode mergeSortList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode fast = head, slow = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    ListNode right = mergeSortList(slow.next);
    slow.next = null;
    ListNode left = mergeSortList(head);
    return mergeTwoSortedLists(left, right);
}
​
private ListNode mergeTwoSortedLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0), p = dummy;
​
    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            p.next = l1;
            l1 = l1.next;
        } else {
            p.next = l2;
            l2 = l2.next;
        }
        p = p.next;
    }
​
    if (l1 != null) p.next = l1;
    if (l2 != null) p.next = l2;
    return dummy.next;
}

（6）合并 K 个有序链表（难）

题干分析

这个题目说的是，给你 K 个递增排序的单链表，你要把它们合成一个链表，并且保持递增排序。合成链表的节点直接使用 K 个链表中的节点即可，无需创建新节点。

# 比如说，给你以下 3 个有序链表：
1 -> 2 -> 4
1 -> 4 -> 8
0 -> 2
​
# 合并后的有序链表是：
0 -> 1 -> 1 -> 2 -> 2 -> 4 -> 4 -> 8

思路解法

思路方法有三：

1. 方法一：最小堆维护，一个个取，一个个构建关系
2. 方法二：两两链表合并
3. 方法三：分治方法

最优的方法是分治方法。

1. 方法一：最小堆维护，一个个取，一个个构建关系

AC 代码：

// Time: O(n*log(k)), Space: O(k), Faster: 70.34%
public ListNode mergeKSortedListsMinHeap(ListNode[] lists) {
    if (lists == null || lists.length == 0) return null;
    Queue<ListNode> q = new PriorityQueue<>((a, b) -> a.val - b.val);
    for (ListNode list: lists)
        if (list != null)
            q.add(list);
    ListNode dummy = new ListNode(0), p = dummy;
​
    while (!q.isEmpty()) {
        ListNode min = q.poll();
        p.next = min;
        p = p.next;
        if (min.next != null) q.add(min.next);
    }
    return dummy.next;
}

1. 方法二：两两链表合并

AC 代码：

// Time: O(k*n), Space: O(1), Faster: 22.49%
public ListNode mergeKSortedListsOneByOne(ListNode[] lists) {
    if (lists == null || lists.length == 0) return null;
    ListNode result = null;
    for (ListNode list: lists) {
        result = mergeTwoSortedLists(result, list);
    }
    return result;
}
​
private ListNode mergeTwoSortedLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0), p = dummy;
​
    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            p.next = l1;
            l1 = l1.next;
        } else {
            p.next = l2;
            l2 = l2.next;
        }
        p = p.next;
    }
​
    if (l1 != null) p.next = l1;
    if (l2 != null) p.next = l2;
    return dummy.next;
}

1. 方法三：分治方法

AC代码：

// Time: O(n*log(k)), Space: O(log(k)), Faster: 100.00%
public ListNode mergeKSortedListsDivideConquer(ListNode[] lists) {
    if (lists == null || lists.length == 0) return null;
    return merge(lists, 0, lists.length-1);
}
​
private ListNode merge(ListNode[] lists, int start, int end) {
    if (start == end) return lists[start];
    if (start > end) return null;
    int mid = start + (end - start) / 2;
    ListNode left = merge(lists, start, mid);
    ListNode right = merge(lists, mid+1, end);
    return mergeTwoSortedLists(left, right);
}
​
private ListNode mergeTwoSortedLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0), p = dummy;
​
    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            p.next = l1;
            l1 = l1.next;
        } else {
            p.next = l2;
            l2 = l2.next;
        }
        p = p.next;
    }
​
    if (l1 != null) p.next = l1;
    if (l2 != null) p.next = l2;
    return dummy.next;
}