[力扣] 剑指 Offer 第二天 - 复杂链表的复制

耐心和持久胜过激烈和狂热。

题目来源

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/fu-za-lian-biao-de-fu-zhi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目描述

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

示例

示例 1

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

示例 2

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

示例 3

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]
1
2

示例 4

输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。
1
2
3

题目解析

如果是普通的链表，我们完全可以遍历链表的过程中复制一个链表，但是复杂链表中存在随机指针，如果是按照原始的方式去拷贝，会存在随机节点没有创建的问题，因此拷贝的前提是【所有节点都已被创建】。既能创建新节点，又能将原节点与新节点一一对应，我们可以使用哈希表去实现。

算法 1

本题是基于 Go 语言去实现

• 定义一个 map，存储结构 → key 为原节点，value 为新节点，初始化 node 指向头结点
• 遍历链表，将原节点和新节点存入 map → 键值对(原节点 : 新节点)
• node 再次指向头结点，再次遍历链表，构建新节点的 next 引用指向和 random 引用指向
• 返回新节点的头结点

代码实现

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

func copyRandomList(head *Node) *Node {
    mp := make(map[*Node]*Node)
    node := head
    for node != nil {
        mp[node] = &Node{Val: node.Val}
        node = node.Next
    }
    node = head
    for node != nil {
        mp[node].Next = mp[node.Next]
        mp[node].Random = mp[node.Random]
        node = node.Next
    }
    return mp[head]    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

执行结果

复杂度分析

时间复杂度：O(N)，遍历两次链表需要 O(N) 的时间复杂度。
空间复杂度：O(N)，其中 N 是链表的长度，为哈希表的额外空间开销。

算法 2

算法优化，遍历链表是无可避免的，因此我们可以从空间的维度去优化 → 去除哈希表的使用。使用另外一种方式，在原链表中做映射关系。
原链表
A → B → C → D
映射之后的链表
A → A' → B → B' → C → C' → D → D'
步骤：

• 判断头结点是否为空，条件成立则直接返回头结点
• 定义新指针 cur 指向头结点，遍历 cur 链表，创建新节点并由原节点的 next 节点指向新节点，做映射关系，然后调节指向。
• cur 重新指向头结点，遍历 cur 链表，构建 ramdom 引用指向，新节点的 random 指向原节点 random 的 next 节点（新 copy 的节点）
• 最后拆分新旧节点，返回新头结点

代码实现

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

func copyRandomList(head *Node) *Node {
    if head == nil {
        return nil
    }
    cur := head
    for cur != nil {
        tmp := &Node{Val:cur.Val}
        tmp.Next = cur.Next
        cur.Next = tmp
        cur = tmp.Next
    }

    cur = head
    for cur != nil {
        if cur.Random != nil {
            cur.Next.Random = cur.Random.Next
        }
        cur = cur.Next.Next
    }

    res := head.Next
    for head != nil {
        next := head.Next
        if next != nil {
        head.Next = next.Next
        }
        head = next
    }
    return res
}
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

执行结果

复杂度分析

时间复杂度：O(N)，遍历两次链表需要 O(N) 的时间复杂度。
空间复杂度：O(1)，创建的新节点所使用的变量使用常数大小的额外空间。

总结

第一种算法使用了 map 结构去实现新旧节点映射，而第二种则以一条线穿插着新旧节点，然后在这条线上构建 copy 后的链表，非常巧妙。

如果本文对你有帮助，欢迎点赞收藏加关注，如果本文有错误的地方，欢迎指正！