[LeetCode] 138. Copy List with Random Pointer

1. Question

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

For example, if there are two nodes X and Y in the original list, where X.random --> Y, then for the corresponding two nodes x and y in the copied list, x.random --> y.

Return the head of the copied linked list.

The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

val: an integer representing Node.val
random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.
Your code will only be given the head of the original linked list.

Example 1:

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2:

Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

Example 3:

Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]

2. Thoughts

Use Greedy
This will be bad for time complexity (O(n)), but can't think of other solutions

3. Tips learned

4. My solution

class Solution:
    def copyRandomList(self, head: "Optional[Node]") -> "Optional[Node]":
        if not head:
            return None

        newhead = Node(head.val)

        iter_newhead = newhead
        iter_head = head
        while iter_head.next:
            iter_head = iter_head.next
            newNode = Node(iter_head.val)
            iter_newhead.next = newNode
            iter_newhead = iter_newhead.next

        iter_newhead = newhead
        iter_newhead_slow = newhead
        iter_head = head
        iter_head_slow = head

        while iter_newhead:
            if iter_head.random == None:
                iter_newhead.random = None
            else:
                while iter_head_slow != iter_head.random:
                    iter_head_slow = iter_head_slow.next
                    iter_newhead_slow = iter_newhead_slow.next
                iter_newhead.random = iter_newhead_slow

                iter_newhead_slow = newhead
                iter_head_slow = head

            iter_head = iter_head.next
            iter_newhead = iter_newhead.next

        return newhead

19/19 cases passed (39 ms)
Your runtime beats 72.19 % of python3 submissions
Your memory usage beats 8.01 % of python3 submissions (18.4 MB)

5. AI Solution and Improvements

Your solution for creating a deep copy of a linked list with random pointers is correct but not optimal in terms of time complexity. The nested loop that updates the random pointers has a time complexity of O(n²), which is not efficient for large lists.

A more efficient approach is to use a hash table to map original nodes to their copies. This way, you can efficiently set the next and random pointers in a single pass through the list. The time complexity of this approach is O(n), and the space complexity is also O(n) due to the extra space used for the hash table.

Here's an improved version of your solution using a hash table:

class Solution:
    def copyRandomList(self, head: "Optional[Node]") -> "Optional[Node]":
        if not head:
            return None

        # Creating a hash map to store the mapping from original nodes to copied nodes
        old_to_new = {}

        # Create new nodes and store them in the hash map
        current = head
        while current:
            old_to_new[current] = Node(current.val)
            current = current.next

        # Set the next and random pointers for the copied nodes
        current = head
        while current:
            if current.next:
                old_to_new[current].next = old_to_new[current.next]
            if current.random:
                old_to_new[current].random = old_to_new[current.random]
            current = current.next

        # Return the head of the copied linked list
        return old_to_new[head]

Explanation:

• First, we iterate through the original list and create a new node for each original node. We store the mapping of original nodes to their copies in a hash table old_to_new.
• Then, in a second pass, we use the hash table to set the next and random pointers for each new node.
• Finally, we return the head of the new list, which is the copy of the original list's head node.

This solution ensures that each node and its relationships are duplicated exactly, and the process is more efficient than your original approach.