LeetCode 138. Copy List with Random Pointer

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:

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

/*
// 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 Solution {
    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%

class Solution {
    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;
    }
}