[LeetCode] Copy List with Random Pointer

 

 

Problem

 

 

 

---

 

Solution

 

Ignore the random pointers for now. We need a way to make the next property point to a new node.

First, create new nodes with original values in the linked list and plug them after the node of the original value. 

Then we can work through the interweaved list and take care of random pointers for the new nodes.

Lastly, break the next links so that old nodes point to old nodes and new nodes point to new nodes only.

Return the head of the new linked list.

 

 

Time Complexity

O(N)

 

 

Space Complexity

O(1)

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

class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: Node
        :rtype: Node
        """
        if not head:
            return head
        
        # interweave old list with copy nodes
        curr = head
        while curr:
            newNode = Node(curr.val)
            newNode.next = curr.next
            curr.next = newNode
            
            curr = curr.next.next
        
        # copy random pointers
        curr = head
        while curr:
            if curr.random is not None:
                curr.next.random = curr.random.next
            curr = curr.next.next
        
        # get rid of original nodes
        curr_copy = copy = head.next
        curr_origin = head
        while curr_origin:
            curr_origin.next = curr_origin.next.next
            if curr_copy.next:
                curr_copy.next = curr_copy.next.next
            curr_origin = curr_origin.next
            curr_copy = curr_copy.next
            
        return copy