K 个一组翻转链表 · 深拷贝带随机指针的链表

K 个一组翻转链表（LeetCode 25）

每隔 K 个节点翻转一组，不足 K 个时保持原样。

关键：先检查是否有 K 个节点，将这 K 个节点翻转后与前后拼接。

ListNode reverseKGroup(ListNode head, int k) {
    ListNode cur = head;
    int count = 0;
    // 1. 找到第 k 个节点（提前判断是否满 k 个）
    while (cur != null && count < k) { cur = cur.next; count++; }
    if (count < k) return head;  // 不足 k 个，直接返回

    // 2. 翻转这 k 个节点
    ListNode prev = null, p = head;
    for (int i = 0; i < k; i++) {
        ListNode next = p.next;
        p.next = prev;
        prev = p;
        p = next;
    }
    // 3. 递归处理剩余部分，head（翻转后成尾部）连接递归结果
    head.next = reverseKGroup(cur, k);
    return prev;  // prev 是翻转后的头部
}

迭代版本（避免递归栈溢出）：

ListNode reverseKGroupIterative(ListNode head, int k) {
    ListNode dummy = new ListNode(0, head);
    ListNode groupPrev = dummy;

    while (true) {
        // 找到 kth 节点
        ListNode kth = getKth(groupPrev, k);
        if (kth == null) break;

        ListNode groupNext = kth.next;
        // 翻转 [groupPrev.next, kth]
        ListNode prev = groupNext, cur = groupPrev.next;
        while (cur != groupNext) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        ListNode tmp = groupPrev.next;
        groupPrev.next = kth;
        groupPrev = tmp;
    }
    return dummy.next;
}

private ListNode getKth(ListNode curr, int k) {
    while (curr != null && k > 0) { curr = curr.next; k--; }
    return curr;
}

深拷贝带随机指针的链表（LeetCode 138）

每个节点额外有 random 指针，可能指向任意节点或 null。

方法 1：哈希表（O(n) 空间）

Node copyRandomList(Node head) {
    Map<Node, Node> map = new HashMap<>();  // 原节点 → 克隆节点
    Node cur = head;
    // 第一遍：创建所有克隆节点
    while (cur != null) {
        map.put(cur, new Node(cur.val));
        cur = cur.next;
    }
    // 第二遍：连接 next 和 random
    cur = head;
    while (cur != null) {
        map.get(cur).next = map.get(cur.next);
        map.get(cur).random = map.get(cur.random);
        cur = cur.next;
    }
    return map.get(head);
}

方法 2：原地（O(1) 空间，三步走）

1. 在每个原节点后插入克隆节点：A → A' → B → B' → ...
2. 设置克隆节点的 random 指针
3. 拆分两个链表

Node copyRandomListO1(Node head) {
    if (head == null) return null;
    // 1. 插入克隆节点
    Node cur = head;
    while (cur != null) {
        Node cloned = new Node(cur.val);
        cloned.next = cur.next;
        cur.next = cloned;
        cur = cloned.next;
    }
    // 2. 设置 random
    cur = head;
    while (cur != null) {
        if (cur.random != null) cur.next.random = cur.random.next;
        cur = cur.next.next;
    }
    // 3. 拆分
    Node dummy = new Node(0), cloneCur = dummy;
    cur = head;
    while (cur != null) {
        cloneCur.next = cur.next;
        cur.next = cur.next.next;
        cloneCur = cloneCur.next;
        cur = cur.next;
    }
    return dummy.next;
}

对比