Copy a postings list

You are given a postings list, where each node in the linked list has 2 pointers, one pointing to the next node and other pointing to a random node in the list. Duplicate this list.

Solution

• Duplicate each node and carefully link the duplicate node t the next node in the list

    def duplicate_list(head)
        curr = head
  
        while curr != nil
            duplicate = Node.new(curr.data)
            duplicate.next = curr.next
            curr.next = duplicate
            curr = duplicate.next
        end
    end
  

• Now, for each node update the jump pointer appropriately, using the the fact that the jump pointer of a node in the new list must point to the jump_ptr.next of the original list (since the duplicate is the next node for every node in original list)

    def update_jump_ptr(head)
        curr = head
  
        while curr != nil
            curr.next.jump = curr.jump.next if curr.jump != nil
            curr = curr.next.next if curr.next != nil
        end
    end
  

• Separate the duplicate nodes from the original list into its own list and return its head

    def update_next_ptr(head)
        prev = head
        new_head = prev.next
        curr = prev.next
  
        while curr != nil
            prev.next = curr.next
            curr.next = curr.next.next if curr.next != nil
            prev = prev.next
            curr = curr.next
        end
  
        new_head
    end
  

Complexity

• Time complexity: O(n) - since we are traversing the list constant (3) times.
• Space complexity: We did not use any additional storage to keep track of the jump pointers.