138. 复制带随机指针的链表/面试题35. 复杂链表的复制(一般)

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

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

我们用一个由 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。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/copy-list-with-random-pointer

思路1：

回溯，遍历，使用一个hashmap接收。递归结束：如果中包含了该节点，直接返回

思路2：

剑指offer上的思路

通过扭曲原来的链表，并将每个拷贝节点都放在原来对应节点的旁边。这种旧节点和新节点交错的方法让我们可以在不需要额外空间的情况下解决这个问题。让我们看看这个算法如何工作

  1. 遍历原来的链表并拷贝每一个节点，将拷贝节点放在原来节点的旁边，创造出一个旧节点和新节点交错的链表。

    如你所见，我们只是用了原来节点的值拷贝出新的节点。原节点 next 指向的都是新创造出来的节点。

    cloned_node.next = original_node.next

    original_node.next = cloned_node

  2. 迭代这个新旧节点交错的链表，并用旧节点的 random 指针去更新对应新节点的 random 指针。比方说， B 的 random 指针指向 A ，意味着 B’ 的 random 指针指向 A’ 。

  3. 现在 random 指针已经被赋值给正确的节点， next 指针也需要被正确赋值，以便将新的节点正确链接同时将旧节点重新正确链接。

代码1：

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
/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    HashMap<Node, Node> map =new HashMap<Node, Node>();
    public Node copyRandomList(Node head) {
        if(head == null)
            return null;
        if(map.containsKey(head))
            return map.get(head);
        //建一个新节点
        Node node = new Node(head.val,null,null);
        map.put(head,node);
        //回溯，递归
        node.next = copyRandomList(head.next);
        node.random = copyRandomList(head.random);   
        return node;
    }
}

代码2：

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

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

class Solution {
    public Node copyRandomList(Node head) {
        if(head == null)
            return null;
        Node node = head;
        Node node2;
        while(node != null){
            //克隆节点
            node2 = new Node(node.val);
            node2.next = node.next;
            node.next = node2;
            node = node2.next;
        }
        //重新指向头
        node = head;
        while(node != null){
            //random
            if(node.random!=null)
                node.next.random = node.random.next;
            else
                node.next.random = null;
            node = node.next.next;
        }
        //继续重新指向头
        node = head;
        //next
        Node node3 = head.next;
        while(node!=null){
            node2 = node.next;
            node.next = node2.next;
            if(node2.next!=null){
                node2.next = node2.next.next;
            }
            node = node.next;
        }
        return node3;

    }
}