Leetcode 138. Copy List with Random Pointer

https://leetcode.com/problems/copy-list-with-random-pointer/

There are mainly two solutions. Solution 1 is to generate a linked list in place and split it as the new list; solution 2 is to copy a new linked list. Solution 2 is easier, though it used an extra dictionary.

Solution 1:

# T:O(n) S:O(n)
class Solution:
    # @param head, a RandomListNode
    # @return a RandomListNode
    def copyRandomList(self, head):
        # copy and combine copied list with original list
        current = head
        while current:
            copied = RandomListNode(current.label)
            copied.next = current.next
            current.next = copied
            current = copied.next
        
        # update random node in copied list
        current = head
        while current:
            if current.random:
                current.next.random = current.random.next
            current = current.next.next
        
        # split copied list from combined one
        dummy = RandomListNode(0)
        copied_current, current = dummy, head
        while current:
            copied_current.next = current.next
            current.next = current.next.next
            copied_current, current = copied_current.next, current.next
        return dummy.next

Run Time: 124 ms

Solution 2:

# T:O(n) S:O(n)
class Solution:
    # @param head, a RandomListNode
    # @return a RandomListNode
    def copyRandomList(self, head):
        dummy = RandomListNode(0)
        current, prev, copies = head, dummy, {}
        
        while current:
            copied = RandomListNode(current.label)
            copies[current] = copied
            prev.next = copied
            prev, current = prev.next, current.next
        
        current = head
        while current:
            if current.random:
                copies[current].random = copies[current.random]
            current = current.next
        
        return dummy.next

Run Time: 152 ms