首页 > itarticle > leetcode 138. copy list with random pointer

leetcode 138. copy list with random pointer

admin 11月 13, 2020 0

138. Copy List with Random Pointer

Difficulty: Medium

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 of the list.

Example 1:

1
2
3
4
5
6
 
Input:
{"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}

Explanation:
Node 1's value is 1, both of its next and random pointer points to Node 2.
Node 2's value is 2, its next pointer points to null and its random pointer points to itself.

Note:

  1. You must return the copy of the given head as a reference to the cloned list.

Solution

Language: 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
40
41
 

// Definition for a Node.
class Node {
    public int val;
    public Node next;
    public Node random;
​
    public Node() {}
​
    public Node(int _val,Node _next,Node _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};
*/
class  {
    public Node copyRandomList(Node head) {
        if (head == null) {
            return head;
        }
        Map<Node, Node> map = new HashMap<>();
        map.put(null, null);
        Node cur = head;
        while (cur != null) {
            if (!map.containsKey(cur)) {
                Node copy = new Node(cur.val);
                map.put(cur, copy);
            }
            cur = cur.next;
        }
        cur = head;
        while (cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
        
    }
}

使用next指针当做映射 100%

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
 
class  {
    public Node copyRandomList(Node head) {
        if (head == null) {
            return head;
        }
        Node cur = head;
        while (cur != null) {
            Node newNode = new Node(cur.val);
            newNode.next = cur.next;
            cur.next = newNode;
            cur = newNode.next;
        }
        cur = head;
        Node newHead = head.next;
        Node newCur = newHead;
        while (cur != null) {
            if (cur.random != null) {
                newCur.random = cur.random.next;
            }
            cur = newCur.next;
            if (cur != null) {
                newCur = cur.next;
            }
        }
        cur = head;
        newCur = newHead;
        while (cur != null) {
            cur.next = newCur.next;
            if (cur.next != null) {
                newCur.next = cur.next.next;
            }
            cur = cur.next;
            newCur = newCur.next;
        }
        return newHead;
    }
}
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能