链表专题 - 简书

例题目录

1、反转链表【简单】
- 反转链表II【中等】
- 重排链表【中等】
2、排序链表【中等】
3、复制带随机指针的链表【中等】
4、二叉树与双向链表【中等】
- 有序链表转换二叉搜索树

例题

1、leetcode 206. 反转链表

1.1 题目描述：

反转一个单链表。

1.2 算法

方法一迭代
从前往后移动每个节点

public class Solution {
    // 方法一 从前往后移动每个节点
    public ListNode reverseList(ListNode head) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        while (head != null && head.next != null) {
            ListNode tmp = head.next;
            ListNode next = dummy.next;
            dummy.next = tmp;
            head.next = tmp.next;
            tmp.next = next;
        }
        return dummy.next;
    }
}

方法二递归
1 -> 2 -> 3 -> 4
1 -> 2 3 <- 4
1 2 <- 3 <- 4
1 <- 2 <- 3 <- 4

public class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode p = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return p;
    }
}

方法三双指针修改指向关系
从前往后遍历每个节点，然后修改每个节点的指向关系

public class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null) return null;
        ListNode pre = null, cur = head;
        ListNode tmp;
        while (cur != null) {
            tmp = cur;
            cur = cur.next;
            tmp.next = pre;
            pre = tmp;
        }
        return pre;
    }
}

1.3 进阶

92. 反转链表 II
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
使用类似于方法一

public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        int idx = 0;
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        cur.next = head;
        while (head != null && head.next != null) {
            idx++;
            if (idx < m) {
                dummy = dummy.next;
                head = head.next;
            } else if (idx >= m && idx < n) {
                ListNode tmp = head.next;
                ListNode next = dummy.next;
                dummy.next = tmp;
                head.next = tmp.next;
                tmp.next = next;
            } else break;
        }
        return cur.next;
    }
}

143. 重排链表
给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
步骤：1. 找到链表中点；2. 翻转后半部分；3. 重组
空间复杂度要求O(1)

class Solution {
    // 先找到中点，然后翻转后半段，再拼装。
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode secondHead = reverse(slow.next);
        slow.next = null;
        while (secondHead != null) {
            ListNode t = head.next;
            head.next = secondHead;
            secondHead = secondHead.next;
            head.next.next = t;
            head = t;
        }
    }

    private ListNode reverse(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode root = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return root;
    }
}

2、leetcode 148. 排序链表

2.1 题目描述：

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

2.2 算法

归并排序思想

方法一递归
由于递归需要调用栈，因此不满足空间时间复杂度的要求。

public class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode tmp = slow.next;
        slow.next = null;
        ListNode left = sortList(head);
        ListNode right = sortList(tmp);
        return mergeSort(left, right);
    }

    private ListNode mergeSort(ListNode left, ListNode right) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while (left != null && right != null) {
            if (left.val < right.val) {
                cur.next = left;
                left = left.next;
            } else {
                cur.next = right;
                right = right.next;
            }
            cur = cur.next;
        }
        cur.next = left == null ? right : left;
        return dummy.next;
    }
}

方法二迭代
自底向上
step=1: (3->4)->(1->7)->(8->9)->(2->11)->(5->6)
step=2: (1->3->4->7)->(2->8->9->11)->(5->6)
step=4: (1->2->3->4->7->8->9->11)->5->6
step=8: (1->2->3->4->5->6->7->8->9->11)
空间 O(1)

public class Solution {
    public ListNode sortList(ListNode head) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        // 统计链表长度
        int n = 0;
        ListNode p = head;
        while (p != null) {
            p = p.next;
            ++n;
        }
        // 控制step一组
        for (int step = 1; step < n; step <<= 1) {
            // 一次完了归置cur和tail
            ListNode cur = dummy.next;
            ListNode tail = dummy;
            while (cur != null) {
                ListNode left = cur;
                ListNode right = cut(cur, step);
                cur = cut(right, step);
                tail.next = merge(left, right);
                while (tail.next != null) tail = tail.next;  // 保持 tail 为尾部
            }
        }
        return dummy.next;
    }

    // 切除前n个节点，返回后半部分的头节点
    private ListNode cut(ListNode node, int step) {
        for (int i = 0; i < step - 1 && node != null; i++) {
            node = node.next;
        }
        if (node == null) return null;
        ListNode p = node.next;
        node.next = null;
        return p;
    }

    // 双路归并
    private ListNode merge(ListNode left, ListNode right) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while (left != null && right != null) {
            if (left.val < right.val) {
                cur.next = left;
                left = left.next;
            } else {
                cur.next = right;
                right = right.next;
            }
            cur = cur.next;
        }
        cur.next = left != null ? left : right;
        return dummy.next;
    }
}

2.3 进阶

147. 对链表进行插入排序
指定插入排序

class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode dummy = new ListNode(Integer.MIN_VALUE);
        dummy.next = head;
        int max = head.val;
        ListNode cur = head.next;
        ListNode tail = head;  // 重要：记录前面有序部分的末尾节点
        while (cur != null) {
            if (cur.val >= max) {
                max = cur.val;
                cur = cur.next;
                tail = tail.next;
            } else {
                ListNode p = dummy;
                while (p.next.val <= cur.val) {
                    p = p.next;
                }
                ListNode t = p.next;
                p.next = cur;
                cur = cur.next;
                p.next.next = t;
                tail.next = cur;
            }
        }
        return dummy.next;
    }
}

3、leetcode 138. 复制带随机指针的链表

3.1 题目描述：

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。

要求返回这个链表的深拷贝。

3.2 算法

方法一 DFS
解题的关键在于用一个map记录已经复制过的节点，key原节点，value为复制后节点。每当new一个新节点时就往map中put。

public class Solution {
     // 方法一 DFS
    Map<Node, Node> visited;

    public Node copyRandomList(Node head) {
        visited = new HashMap<>();
        return dfs(head);
    }

    private Node dfs(Node node) {
        if (node == null) return null;
        if (visited.containsKey(node)) return visited.get(node);
        Node nodeCopy = new Node(node.val);
        visited.put(node, nodeCopy);
        nodeCopy.next = dfs(node.next);
        nodeCopy.random = dfs(node.random);
        return nodeCopy;
    }
}

方法二 BFS
用一个队列保存以及复制过的节点，同时map记录复制过的节点，出队的节点检查next节点和random节点，当还没复制，就复制一份并加入队列。直到队列为空。

public class Solution {
    // 方法二 BFS
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        Queue<Node> queue = new LinkedList<>();
        Map<Node, Node> visited = new HashMap<>();
        Node headCopy = new Node(head.val);
        visited.put(head, headCopy);
        queue.add(head);
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            if (node.next != null && !visited.containsKey(node.next)) {
                visited.put(node.next, new Node(node.next.val));
                queue.add(node.next);
            }
            if (node.random != null && !visited.containsKey(node.random)) {
                visited.put(node.random, new Node(node.random.val));
                queue.add(node.random);
            }
            visited.get(node).next = visited.get(node.next);
            visited.get(node).random = visited.get(node.random);
        }
        return headCopy;
    }
}

方法三迭代
创建dummy节点，按顺序遍历节点饼复制，同时检查next节点和random节点，如还未复制则复制。复制记录保存在map visited中。

public class Solution {
    // 方法三 迭代
    Map<Node, Node> visited;
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        visited = new HashMap<>();
        Node dummy = new Node(-1);
        Node first = dummy;
        while (head != null) {
            dummy.next = copyNode(head);
            dummy = dummy.next;
            dummy.next = (head.next != null) ? copyNode(head.next) : null;
            dummy.random = (head.random != null) ? copyNode(head.random) : null;
            head = head.next;
        }
        return first.next;
    }

    private Node copyNode(Node node) {
        if (visited.containsKey(node)) return visited.get(node);
        Node nodeNew = new Node(node.val);
        visited.put(node, nodeNew);
        return nodeNew;
    }
}

方法四优化后的迭代
方法三中的迭代需要用到visited记录复制过的节点，占用了O(n)的空间。一个比较trick的方法是把每个复制后的节点连在原节点之后，后面再断开连接，就避免的使用map来记录复制过的节点。
步骤：1.复制节点 2.复制随机指针 3.断裂

public class Solution {
    // 方法四 优化迭代 空间复杂度O(1)
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        // 复制节点
        Node cur = head;
        while (cur != null) {
            Node tmp = new Node(cur.val);
            Node next = cur.next;
            cur.next = tmp;
            tmp.next = next;
            cur = next;
        }
        // 复制随机指针
        cur = head;
        while (cur != null) {
            if (cur.random != null) {
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }
        // 断裂
        Node dummyNew = new Node(-1);
        Node curNew = dummyNew;
        cur = head;
        while (cur != null) {
            curNew.next = cur.next;
            curNew = curNew.next;
            cur.next = cur.next.next;
            cur = cur.next;
        }
        return dummyNew.next;
    }
}

4、剑指 Offer 36. 二叉搜索树与双向链表

4.1 题目描述：

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

4.2 算法

中序遍历，记录前一个节点，对遍历到的节点修改指针的指向。注意首尾节点也要相连。

public class Solution {
    public Node treeToDoublyList(Node root) {
        if (root == null) return null;
        Stack<Node> stack = new Stack<>();
        Node pre = null, first = null;
        while (!stack.empty() || root != null) {
            if (root != null) {
                stack.add(root);
                root = root.left;
            } else {
                root = stack.pop();
                if (pre == null) {
                    first = root;
                } else {
                    pre.right = root;
                    root.left = pre;
                }
                pre = root;
                root = root.right;
            }
        }
        // 连接首尾
        first.left = pre;
        pre.right = first;
        return first;
    }
}

4.3 类似题目

109. 有序链表转换二叉搜索树

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;
        if (head.next == null) return new TreeNode(head.val);
        ListNode pre = null;
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        pre.next = null;
        TreeNode root = new TreeNode(slow.val);
        root.left = sortedListToBST(head);
        root.right = sortedListToBST(slow.next);
        return root;
    }
}