复制含有随机指针节点的链表

发表于 阅读次数：

问题

一种特殊的链表节点类描述如下：

1
2
3
4
5
6
7
8
public class Node {
    public int value;
    public Node next;
    public Node rand;
    public Node(int data){
        this.value = data;
    }
}

该类和正常节点拥有一样的功能，还新增了一个rand指针，可以指向链表钟的任意一个节点，也可以指向null。

请实现一个函数完成这个链表钟所有结构的复制，并返回复制的新链表的头节点。进阶：不用额外的数据结构，只用有限几个遍历，且再时间复杂度为O(N)内完成。

思路

第一眼看这题目可能会觉得很简单，直接遍历然后复制就好啦，其实不然，因为rand指针的存在，可能会随时去到较前的节点，所以需要记录之前的节点，这里提供两个方法。

方法一：

这里我们可以用哈希表，每一个原节点(key)都对应着一个复制节点(value)。把原节点作为key，复制节点作为value。遍历整个链表把每一个原节点，都复制了，再次遍历对复制节点的next和rand进行赋值（因为这时候我们全部节点都有了，你rand想指向哪里就指向哪里）

方法二：

本题的链表有rand指针，但本质上还是指向链表中的其中一个节点而已，只要我们能任意获得链表中的节点就可以了。

这里我们把链表进行一次遍历，让每一个原节点的next指向复制节点，复制节点的next指向原节点的next。这样就形成了一种变相的映射关系，原节点在前，复制节点在后。
随之我再次遍历链表、把复制节点的rand连上，最后再把复制节点分离出来即可。

实现

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
55
56
57
58
59
60
61
62

public static class Node {
        public int value;
        public Node next;
        public Node rand;
        public Node(int data){
            this.value = data;
        }
    }

    //方法一
    public static Node copyListWithRand1(Node head) {
        {
            HashMap<Node, Node> map = new HashMap<>();
            Node current = head;
            while (current != null) {
                map.put(current, new Node(current.value));
                current = current.next;
            }
            current = head;
            while (current != null) {
                map.get(current).next = map.get(current.next);
                map.get(current).rand = map.get(current.rand);
                current = current.next;
            }
            return map.get(head);
        }
    }

    //方法二：
    public static Node copyListWithRand2(Node head) {

        Node current = head;
        Node nextNode = null;
        while (current != null) {
            nextNode = current.next;
            current.next = new Node(current.value);
            current.next.next = nextNode;   //1'->2
            current = nextNode; //1->2
        }
        current = head;
        while(current != null) {
            current.next.rand = current.rand == null ? null : current.rand.next;
            current = current.next.next;
        }

        //拆出来就好了，为什么不能在复制rand的同时拆出来？因为你rand可能需要前面的节点，如果你拆了前面的节点你怎么拿
        current = head;
        Node ret = head.next;

        //当前链表：1->1'->2->2'->3->3'...
        //原链表：  1->2->3...
        //目标：    1'->2'->3'...
        while(current != null) {
            //nextNode就是原链表的那些节点1->2->3...
            nextNode = current.next.next;
            current.next.next = nextNode != null ? nextNode.next: null;
            current.next = nextNode;
            current = current.next;
        }
        return ret;
    }

这里建议兄弟萌按照图，一点一点自己写，上面的代码仅供参考