Clone a Linked List with Next and Random Pointers You are giv | Cse interview questions

Clone a Linked List with Next and Random Pointers

You are given a linked list where each node can have two pointers. One pointer pointes to next node as usual. Apart from this there is an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

Constraints :

-10000 <= node.value <= -10000
Number of nodes <= 1000

Examples :

Let us say linked list of n nodes is represented as a list of nodes where each node is of form [value, random_index]. value denotes value of data and random_index denotes the index of the node to which random pointer points to. It can range from 0 to n-1, or null if it does not point to any node.

There is also a next pointer which points to next node (or null for last node) as usual.

Input 1 : head_in = [[1,1], [2,1], [3,1]]

Output 1 : head_out = [[1,1], [2,1], [3,1]]

Explanation 1 :

Input list has three nodes with values 1, 2 and 3. Random pointers of all three points to node with index 1 (0-based) which is middle node. Clone of input list is returned.

Input 2 : head_in = [[1,null], [15,1], [101,null], [93,0]]

Output 2 : head_out = [[1,null], [15,1], [101,null], [93,0]]

Explanation 2 :

Input list has four nodes with values 1, 15, 101 and 93. All three points to node with index 1 (0-based) which is middle node.

Random pointer of 0th node points to null, 1st node points to itself, 2nd node again points to null and third node points to 0th node.

Clone of input list is returned.

Topic : Linked Lists

Reference(s) ->
GeeksforGeeks, LeetCode

Solution ->

GFG Article Set 1, Set 2

For implementation in O(1) space, refer this article

Asked in Amazon

Join our Official Channel @cseinterview