剑指 Offer 35. 复杂链表的复制

题目描述

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 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
29


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

func copyRandomList(head *Node) *Node {
    record := make(map[*Node]*Node)

    var dfs func(root *Node) *Node
    dfs = func(root *Node) *Node {
        if nil == root {
            return nil
        }
        if ret, ok := record[root]; ok {
            return ret
        }
        newNode := &Node{Val: root.Val}
        record[root] = newNode
        newNode.Next = dfs(root.Next)
        newNode.Random = dfs(root.Random)
        // record[root] = newNode 不能放在这里，会导致无限循环。
        return newNode
    }
    return dfs(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
25
26
27
28
29
30
31
32


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

func copyRandomList(head *Node) *Node {
    if head == nil {
        return nil
    }
    for node := head; node != nil; node = node.Next.Next {
        next := node.Next
        node.Next = &Node{Val: node.Val, Next: next}
    }
    for node := head; node != nil; node = node.Next.Next {
        if node.Random != nil {
            node.Next.Random = node.Random.Next
        }
    }
    newHead := head.Next
    for node := head; node != nil; node = node.Next {
        oldNext := node.Next.Next
        if oldNext != nil {
            node.Next.Next = oldNext.Next
        }
        node.Next = oldNext
    }
    return newHead
}