138. Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

 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
/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null){
            return null;
        }
        Map<RandomListNode,RandomListNode> map = new HashMap<RandomListNode,RandomListNode>();

        /*
        * 节点意义复制到map中
        * */
        RandomListNode point = head;
        while(point!=null){
            map.put(point,new RandomListNode(point.label));
            point = point.next;
        }
        /*
        * 指针重新指向开头的地方
        * */
        point = head;
        while(point!=null){
            map.get(point).next = map.get(point.next);
            map.get(point).random = map.get(point.random);
            point = point.next;
        }
        return map.get(head);
    }
}

带随机指针链表的深拷贝: - 做的不明所以 - 步骤能能够理解,但是效率不高,之后可以再改进 - 最近一周实在是效率低下,装机也要适可而止,不能影响到日常生活