Clone a linked list with next and random pointer in O(1) space

Introduction

One of the most crucial data structures to learn while preparing for interviews is the linked list. In a coding interview, having a thorough understanding of Linked Lists might be a major benefit.

Problem Statement

In this problem, we are given a linked list of length N having two pointers in each node. The first pointer points to the next node of the list, and the second one is a random pointer which can point to any node of the linked list, or NULL. Now we are asked to write a program that clones the given list in O(1) space.

Note: The cloned linked list should consist of exactly N new nodes, where the value of each node is the same as the corresponding value in original linked list and the next and random pointers of the new nodes should point to new nodes in the cloned linked list in such a way that the pointers in the original linked list and cloned linked state represent the same list state. Finally, you have to return the head of the cloned linked list.

Problem statement understanding

First, we need to understand what cloning a linked list means.

  • Cloning means copying the linked list without changing the structure and the data inside it. Addresses of the nodes will change as new nodes will be created for the cloned list.

From the above figure, we can see that the addresses of the cloned nodes are different, but the structure and data of the linked list are the same.

  • So basically, first, we have to clone a linked list and then return the head of the cloned linked list as output.
Example

Input linked list

Output: A new linked list that is a copy of the original list

Now I think from the above examples, the problem statement is clear. So let’s see how we will approach it. Any Ideas?

  • If not, it’s okay. We will see in the next section thoroughly how we can approach this problem.

Let’s move to the next section.

Approach

Our approach will be simple:

  • We will make a copy of the given linked list so that the next pointer of every node will be simply pointing to the copy of the next node.
  • But for the random pointer, we will find out which node number it is pointing at in the original linked list.
    • For example, in the original linked list the random pointer of 1st node is pointing to the 3rd node so we can see that in the cloned list also the random pointer of the first node is pointing to the third node.
    • For doing this in the O(n) time complexity. We will use a clever technique. What we will do is that we will make a copy of the node and put it between the node and node->next. In this way we will observe that we can do the assignment of random pointers in O(1) time for every n node.
  • Finally, after random pointer linking, we will separate the cloned list from the sequence of original and copied nodes and output the cloned linked list.

Let’s move to the algorithm section to see the above approach step by step in detail.

Algorithm

  • We will first create a copy of 1st node and insert it between 1st node and 2nd in the original linked list.
  • Similarly, we will create a copy of 2nd and will insert it between 2nd and 3rd node. We will continue in this manner and add the copy of node Xth between Xth node and (X+1)th node. The example given below will help you to understand this step better.
    • If A -> B -> C is our original linked list, then the linked list after the above steps of adding a copy of Xth between Xth and (X+1)th node will be be A -> A’ -> B -> B’ -> C -> C’.
  • Now we will link the random pointers of the newly created nodes in the following manner:
    • original->next->random = original->random->next.
    • Why does this work? This works because original->next is simply a copy of the original and original->random->next is simply a copy of the random.
  • Now we will restore the original and cloned linked lists in the below manner by using a single loop.
    • original->next = original->next->next
    • copy->next = copy->next->next
  • Taking the previous example only, A -> B -> C is the original list and the cloned list will be A’ -> B’ -> C’.
  • Make sure that original->next is NULL and finally return the head of the cloned list.

Dry Run

Code Implementation

#include<stdio.h>
#include<stdlib.h>

struct Node
{
    int data;
    struct Node *next;
    struct Node *random;
    
};

struct Node *newNode(int x)
{
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    temp->data = x;
    temp->next = NULL;
    return temp;
}
 
// Utility function to print the list.
void print(struct Node *start)
{
    struct Node *ptr = start;
    while (ptr)
    {
        printf(" Data = %d",ptr->data);
        printf(" , Random  = %d\n",ptr->random->data);
        //printf("\n");
        ptr = ptr->next;
    }
}
 
// This function clones a given linked list
// in O(1) space
struct Node* clone(struct Node *start)
{
   struct Node* curr = start;
   struct Node *temp;
 
    // insert additional node after
    // every node of original list
    while (curr)
    {
        temp = curr->next;
 
        // Inserting node
        //struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
        curr->next = newNode(curr->data);
        curr->next->next = temp;
        curr = temp;
    }
 
    curr = start;
 
    // adjust the random pointers of the
    // newly added nodes
    while (curr)
    {
        if(curr->next)
            curr->next->random = curr->random ?
                                 curr->random->next : curr->random;
 
        // move to the next newly added node by
        // skipping an original node
        curr = curr->next?curr->next->next:curr->next;
    }
 
    struct Node* original = start;
    struct Node* copy = start->next;
 
    // save the start of copied linked list
    temp = copy;
 
    // now separate the original list and copied list
    while (original && copy)
    {
        original->next =
         original->next? original->next->next : original->next;
 
        copy->next = copy->next?copy->next->next:copy->next;
        original = original->next;
        copy = copy->next;
    }
 
    return temp;
}
 
// Driver code
int main()
{
    struct Node* start = newNode(1);
    start->next = newNode(2);
    start->next->next = newNode(3);
    start->next->next->next = newNode(4);
    start->next->next->next->next = newNode(5);
 
    // 1's random points to 3
    start->random = start->next->next;
 
    // 2's random points to 1
    start->next->random = start;
 
    // 3's and 4's random points to 5
    start->next->next->random =
                    start->next->next->next->next;
    start->next->next->next->random =
                    start->next->next->next->next;
 
    // 5's random points to 2
    start->next->next->next->next->random =
                                      start->next;
 
    printf( "Original list : \n");
    print(start);

    printf( "\nCloned list : \n");
    struct Node *cloned_list = clone(start);
    print(cloned_list);
 
    return 0;
}
#include <bits stdc++.h>
using namespace std;
 
/* Structure of a node */
struct Node
{
    int data;
    Node *next,*random;
    Node(int a)
    {
        data = a;
        next = NULL;
      random = NULL;
    }
};

/* This function is used to print the linked list */
void printingLinkedList(Node *head)
{
    Node *ptr = head;
    while (ptr != NULL)
    {
        cout << "Data = " << ptr->data << ", Random  = " << ptr->random->data << endl;
        ptr = ptr->next;
    }
}

/* This function will return the cloned linked list */
Node* cloningLinkedList(Node *head)
{
    Node* curr = head, *temp;
    while (curr != NULL)
    {
        temp = curr->next;
        curr->next = new Node(curr->data);
        curr->next->next = temp;
        curr = temp;
    }
    curr = head;
 
    while (curr != NULL)
    {
        if(curr->next)
            curr->next->random = curr->random ?
                                 curr->random->next : curr->random;
        curr = curr->next?curr->next->next:curr->next;
    }
 
    Node* original = head, *copy = head->next;
    temp = copy;
 
    while ((original !=NULL) && (copy != NULL))
    {
        original->next = original->next? original->next->next : original->next;
        copy->next = copy->next?copy->next->next:copy->next;
        original = original->next;
        copy = copy->next;
    }
    return temp;
}

int main()
{
    Node* head = new Node(1);
    head->next = new Node(3);
    head->next->next = new Node(5);
    head->next->next->next = new Node(7);
 
    head->random = head->next->next;
    head->next->random = head->next->next->next;
    head->next->next->random = head->next;
    head->next->next->next->random = head;
                                       
    cout << "Original linked list : \n";
    printingLinkedList(head);
    cout << "\nCloned linked list : \n";
    Node *clone = cloningLinkedList(head);
    printingLinkedList(clone);
    return 0;
}
class Clone {
 
    // Structure of linked list Node
    static class Node {
        int data;
        Node next, random;
        Node(int x)
        {
            data = x;
            next = random = null;
        }
    }
 
    // Utility function to print the list.
    static void print(Node start)
    {
        Node ptr = start;
        while (ptr != null) {
            System.out.println("Data = " + ptr.data
                               + ", Random = "
                               + ptr.random.data);
            ptr = ptr.next;
        }
    }
 
    // This function clones a given
    // linked list in O(1) space
    static Node clone(Node start)
    {
        Node curr = start, temp = null;
        while (curr != null) {
            temp = curr.next;
            curr.next = new Node(curr.data);
            curr.next.next = temp;
            curr = temp;
        }
        curr = start;
        while (curr != null) {
            if (curr.next != null)
            {
                curr.next.random = (curr.random != null)? curr.random.next: curr.random;
            }
            curr = curr.next.next;                   
        }
 
        Node original = start, copy = start.next;
        temp = copy;
        while (original != null) {
            original.next =original.next.next;
 
          copy.next = (copy.next != null) ? copy.next.next
                                            : copy.next;
            original = original.next;
            copy = copy.next;
        }
        return temp;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        Node start = new Node(1);
        start.next = new Node(2);
        start.next.next = new Node(3);
        start.next.next.next = new Node(4);
        start.next.next.next.next = new Node(5);
 
        start.random = start.next.next;
        start.next.random = start;
 
        start.next.next.random = start.next.next.next.next;
        start.next.next.next.random
            = start.next.next.next.next;
 
        start.next.next.next.next.random = start.next;
 
        System.out.println("Original list : ");
        print(start);
 
        System.out.println("Cloned list : ");
        Node cloned_list = clone(start);
        print(cloned_list);
    }
}
'''Structure of linked list node'''
class Node:
	def __init__(self, data):
		self.data = data
		self.next = None
		self.random = None

# This function will return the cloned linked list
def cloningLinkedList(original_root):
	curr = original_root
	while curr != None:
		new = Node(curr.data)
		new.next = curr.next
		curr.next = new
		curr = curr.next.next

	curr = original_root
	while curr != None:
		curr.next.random = curr.random.next
		curr = curr.next.next

	curr = original_root
	dup_root = original_root.next
	while curr.next != None:
		tmp = curr.next
		curr.next = curr.next.next
		curr = tmp

	return dup_root

# This function is used to print the linked list 
def printingLinkedList(root):

	curr = root
	while curr != None:
		print('Data =', curr.data, ', Random =', curr.random.data)
		curr = curr.next


head = Node(1)
head.next = Node(3)
head.next.next = Node(5)
head.next.next.next = Node(7)

head.random = head.next.next
head.next.random = head.next.next.next
head.next.next.random = head.next
head.next.next.next.random = head

print('Original list:')
printingLinkedList(head)
cloningLinkedListd_list = cloningLinkedList(head)
print('\ncloningLinkedListd list:')
printingLinkedList(cloningLinkedListd_list)

Output

Original linked list :
Data = 1, Random = 5
Data = 3, Random = 7
Data = 5, Random = 3
Data = 7, Random = 1

Cloned linked list :
Data = 1, Random = 5
Data = 3, Random = 7
Data = 5, Random = 3
Data = 7, Random = 1

Time Complexity: O(N), since we are only traversing over the length of the linked list.

[forminator_quiz id=”4907″]

So, in this article, we have tried to explain the most efficient approach to rearrange a given linked list in place. This is an important problem when it comes to coding interviews. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes visit Linked List.

Leave a Reply

Your email address will not be published. Required fields are marked *