138.复制带随即指针的链表

题目描述

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

构造这个链表的深拷贝。深拷贝应该正好由 n 个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入 / 输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

你的代码只接受原链表的头节点 head 作为传入参数。

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]

输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

输入：head = [[1,1],[2,1]]

输出：[[1,1],[2,1]]

示例 3：

输入：head = [[3,null],[3,0],[3,null]]

输出：[[3,null],[3,0],[3,null]]

提示：

0 <= n <= 1000
-10⁴ <= Node.val <= 10⁴
Node.random 为 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
27
28


/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Next *Node
 *     Random *Node
 * }
 */

func copyRandomList(head *Node) *Node {
    record := map[*Node]*Node{}
    var _copy func(head *Node) *Node
    _copy = func(head *Node) *Node {
        if head == nil {
            return head
        }
        if record[head] != nil {
            return record[head]
        }
        newNode := &Node{Val: head.Val}
        record[head] = newNode
        newNode.Next = _copy(head.Next)
        newNode.Random = _copy(head.Random)
        // record[head] = newNode 不能放在这里，会造成无限循环
        return newNode
    }
    return _copy(head)
}

复杂度分析

时间复杂度：O(n)，其中 n 是链表的长度。对于每个节点，我们至多访问其「后继节点」和「随机指针指向的节点」各一次，均摊每个点至多被访问两次。
空间复杂度：O(n)，其中 n 是链表的长度。为哈希表的空间开销。

解法二：迭代 + 节点拆分

 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


func copyRandomList(head *Node) *Node {
    if head == nil {
        return nil
    }
    // 复制每一个节点
    for cur := head; cur != nil; cur = cur.Next.Next {
        next := cur.Next
        newNode := &Node{Val: cur.Val}
        cur.Next = newNode
        newNode.Next = next
    }

    // 设置 Random 指向
    for cur := head; cur != nil; cur = cur.Next.Next {
        if cur.Random != nil {
            cur.Next.Random = cur.Random.Next
        }
    }

    // 设置 Next 指向, 如果没有函数开始对 head == nil 的处理，下面代码会导致程序 panic
    ret := head.Next
    // 注意：此时 for 循环的循环变量更新为 cur = cur.Next 而不是 cur = cur.Next.Next
    for cur := head; cur != nil; cur = cur.Next {
        next := cur.Next
        cur.Next = cur.Next.Next
        if cur.Next != nil {
            next.Next = cur.Next.Next
        }
    }
    return ret
}

思考：如何将一个节点数目为偶数的链表分成两个子链表 a 和 b，a 由所有编号为偶数的节点构成，b 由所有编号为奇数的节点构成，节点从 0 开始编号，头节点的下一个节点编号为 1，依次类推。

可以按照以下步骤将一个节点数目为偶数的链表分成两个子链表 a 和 b：

创建两个新的链表，分别作为子链表 a 和子链表 b。同时创建指向两个子链表头部的指针 a_head 和 b_head。
遍历原链表，对每个节点进行分类。可以根据节点编号的奇偶性来进行分类，其中编号为偶数的节点归到子链表 a 中，编号为奇数的节点归到子链表 b 中。
在遍历过程中，使用指针 a_tail 和 b_tail 分别在子链表 a 和子链表 b 的末尾添加新的节点。
遍历完成后，子链表 a 和子链表 b 就已经分别包含了原链表中所有编号为偶数和奇数的节点。