JZ 35 | LC138 (with template)

Solution to JZ 35 (same as LeetCode 138 Copy List with Random Pointer) and a template for copying a typical linked list.

JZ 35 | LeetCode 138

Copy List with Random Pointer (Hard). [NowCoder link] [LeetCode link]

1. Hash. Use Hashtable to store nodes of original linked list.

   Time complexity O(n), space complexity O(n).

# class RandomListNode:
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None
class Solution:
    def Clone(self, pHead):
        if not pHead: 
          return None
        hash = {}
        
        cur = pHead
        while cur:
            hash[cur] = RandomListNode(cur.label)
            cur = cur.next
            
        cur = pHead
        while cur:
            hash[cur].next = hash.get(cur.next)
            hash[cur].random = hash.get(cur.random)
            cur = cur.next
        return hash[pHead]

2. Duplicate nodes and split linked list.

   Time complexity O(n), space complexity O(1).

# class RandomListNode:
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None
class Solution:
    def Clone(self, pHead):
        if not pHead:
            return pHead
          
        # duplicate each node
        cur = pHead
        while cur:
            copy = RandomListNode(cur.label)
            copy.next = cur.next # link copy to cur.next
            cur.next = copy # link cur to copy
            cur = copy.next # move to copy the next node
            
        # construct random links
        cur = pHead
        while cur:
            if cur.random:
                cur.next.random = cur.random.next
            cur = cur.next.next
            
        # split linked list (double pointer)
        cur = pHead
        newHead = RandomListNode(0) # newHead stays intact
        tmp = newHead # tmp as a pointer to move
        while cur:
            tmp.next = cur.next # link newHead to cur.next
            tmp = tmp.next # move to the next
            cur.next = tmp.next # link cur to tmp next to recover the original linked list
            cur = cur.next
        return newHead.next

Template of Copying a Linked List

dum is the head of the new linked list and it stays intact. We use double pointer pre and cur to copy a linked list.

def copyLinkedList(self, head: 'Node') -> 'Node':
      cur = head
      dum = pre = Node(0)
      while cur:
            node = Node(cur.val) # copy node at cur
            pre.next = node      # link pre to cur
             cur = cur.next       # move cur to cur.next
            pre = node           # move pre to pre.next
            return dum.next