Leaky Cauldron
0%

复制带随机指针的链表

Posted on Edited on

题目 LeetCode # 138

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

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

提示：

  • -10000 <= Node.val <= 10000
  • Node.random 为空（null）或指向链表中的节点。
  • 节点数目不超过 1000 。

题解

方法一: 使用 HashMap

通过使用 HashMap 来建立原结点与复制后结点之间的对应关系, 再遍历原链表建立新结点 random 指针的指向关系

Java

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
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

public class CopyList {
    public static Node copyRandomList(Node head) {
        HashMap<Node, Node> map = new HashMap<>();
        Node tmp1 = head;
        while (tmp1 != null) {
            map.put(tmp1, new Node(tmp1.val));
            tmp1 = tmp1.next;
        }

        Node tmp2 = head;
        while (tmp2 != null) {
            map.get(tmp2).next = map.get(tmp2.next);
            map.get(tmp2).random = map.get(tmp2.random);
            tmp2 = tmp2.next;
        }

        return map.get(head);
    }
}

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Node:
    def __init__(self, x, next=None, random=None):
        self.val = int(x)
        self.next = next
        self.random = random

class CopyList:
    def copy_random_list(self, head):
        list_map = {}
        tmp1 = head
        while tmp1:
            list_map[tmp1] = Node(tmp1.val)
            tmp1 = tmp1.next
        
        tmp2 = head
        while tmp2:
            list_map.get(tmp2).next = list_map.get(tmp2.next)
            list_map.get(tmp2).random = list_map.get(tmp2.random)
            tmp2 = tmp2.next
        
        return list_map.get(head)

方法二: 复制结点

复制原链表结点 ( 如 1->2->3 复制为 1->1->2->2->3->3 ), 再复制 random 指针的指向, 最后将新链表分离.

Java

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
public class Code_13_CopyList {
    public static Node copyRandomList(Node head) {
        if (head == null)
            return null;

        Node tmp = head;
        Node newNode = null;
		
        // 复制结点
        while (tmp != null) {
            newNode = new Node(tmp.val);
            newNode.next = tmp.next;
            tmp.next = newNode;
            tmp = newNode.next;
        }

        tmp = head;
        // 复制 random 指针
        while (tmp != null) {
            newNode = tmp.next;
            newNode.random = tmp.random != null ? tmp.random.next : null;
            tmp = newNode.next;
        }

        tmp = head;
        Node next = null;
        Node result = head.next;
        // 分离新链表, 复原原链表
        while (tmp != null) {
            next = tmp.next.next;
            newNode = tmp.next;
            tmp.next = next;
            newNode.next = next != null ? next.next : null;
            tmp = next;
        }

        return result;
    }
}

Python

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
class Node:
    def __init__(self, x, next=None, random=None):
        self.val = int(x)
        self.next = next
        self.random = random

class CopyList:
    def copy_random_list(self, head):
        if head is None:
            return None
        
        tmp = head
        
        while tmp:
            new_node = Node(tmp.val)
            new_node.next = tmp.next
            tmp.next = new_node
            tmp = new_node.next
            
        tmp = head
        while tmp:
            new_node = tmp.next
            new_node.random = tmp.random.next if tmp.random else None
            tmp = new_node.next
        
        tmp = head
        result = head.next
        while tmp:
            next = tmp.next.next
            new_node = tmp.next
            tmp.next = next
            new_node.next = next.next if next else None
            tmp = next
        
        return result