138. Copy List with Random Pointer

知道就是知道，不知道就是不知道

Key idea: insert copy of each node into original list

核心： 把每个点的副本插入原始的list

0, Original list

1, Copy "next" and "value" into the original list

2, Copy "random"

3, Split original list and copy list, return copy head

Solution:

1. copy next

2. copy random

3. split origin and copy

Don't modify original list when finish copy

Be careful with the case of current.random == null

Java(very efficient)

别忘了最后将orignial list指针next还原

class Solution {
    public Node copyRandomList(Node head) {
        Node dump = new Node(0);
        dump.next = head;
        if(head == null) return null;
        
        // insert new node, copy next
        Node curr = head;
        while(curr != null) {
            Node insert = new Node(curr.val);
            insert.next = curr.next;
            curr.next = insert;
            curr = curr.next.next;
        }
        
        // deep copy random
        curr = head;
        while(curr != null) {
            if(curr.random == null)
                curr.next.random = null;
            else
                curr.next.random = curr.random.next;
            curr = curr.next.next;
        }
        
        // remove original node
        curr = head.next;
        dump.next = curr;
        while(curr.next != null) {
            head.next = head.next.next;
            curr.next = curr.next.next;
            head = head.next;
            curr = curr.next;
        }
        // add tail
        head.next = null;
        curr.next = null;
        
        return dump.next;
    }
}

Python

"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        # ege case
        if head == None:
            return None
        
        # regular case
        self.copyNext(head)
        self.copyRandom(head)
        return self.split(head)
        
    
    def copyNext(self, head):
        while head != None:
            temp = ListNode(head.val)
            temp.next = head.next
            head.next = temp
            head = head.next.next
            
    def copyRandom(self, head):
        while head != None:
            if head.random != None:
                head.next.random = head.random.next
            else:
                head.next.random = None
            head = head.next.next
            
    def split(self, head):
        dummy = ListNode(0)
        head = head.next
        dummy.next = head
        while head.next != None:
            head.next = head.next.next
            head = head.next
        return dummy.next

在split步骤时，在head指针挪动时，每次应该只移动一步head = head.next，因上面一步已经将head.next指向了head.next.next.