Copy List with Random Pointer Python

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the 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) where random pointer points to, or null if it does not point to any node.

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]]
Example 4:
Input: head = []
Output: []
Explanation: Given linked list is empty (null pointer), so return null.

Constraints:
  • -10000 <= Node.val <= 10000
  • Node.random is null or pointing to a node in the linked list.
  • Number of Nodes will not exceed 1000
"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""
class Solution:        
    def copyRandomList(self,head):
        if not head:
            return head
        ptr = head
        while ptr:
            new_node = Node(ptr.val,None,None)
            new_node.next = ptr.next
            ptr.next = new_node
            ptr = new_node.next
            
        ptr = head
        
        while ptr:
            new_node = ptr.next
            new_node.random = ptr.random.next if ptr.random else None
            ptr = new_node.next
            
        old_ptr = head
        new_ptr = head.next
        final_ptr = head.next
        while old_ptr:
            old_ptr.next = old_ptr.next.next if old_ptr.next else None
            new_ptr.next = new_ptr.next.next if new_ptr.next else None
            old_ptr = old_ptr.next
            new_ptr = new_ptr.next
            
        return final_ptr

Time Complexity : O(n)
Space Complexity :O(1)


            

        
            
            
        
            
        
        
        
        

        
        
        
        

No comments:

Post a Comment

Featured Post

H1B Visa Stamping at US Consulate

  H1B Visa Stamping at US Consulate If you are outside of the US, you need to apply for US Visa at a US Consulate or a US Embassy and get H1...