Clone a Linked List with a next and random pointer

Coding Sep 15, 2020

Introduction

Given a double linked list with one pointer pointing to the next node similar to single linked list. The second pointer can point to any node in the linked list. We have to write a program in O(n) time.

Approach

We can have a copy of the original nodes, create random links and separate original from cloned. This three step approach listed below.

Flow diagram for cloning the Linked List with Random Pointer
  1. We clone the copy of node in the original Linked List next to the original node.
Flow Diagram to copy the original node

2. We use the random pointer from the original nodes to add them in the copied node based on the next node.

Flow diagram to copy the random pointer and separate the cloned head

3. Finally, we separate the original and cloned head.

Pseudo Code

Sample Pseudo code for the logic
/*
class Node {
    int data;
    Node next, arb;

    Node(int d) 
    { 
        data = d;
        next = arb = null; 
        
    }
}*/
// function to copy linked list
class Clone {
    Node copyList(Node head) {
        // 1. clone across next links
        Node node = head;
        while (node != null) {
            Node nodeCopy = new Node(node.data);
            Node l = node.next;
            node.next = nodeCopy;
            nodeCopy.next = l;
            node = l;
        }
        // 2. Set Random/arb Pointer
        node = head;
        while (node != null) {
            Node nodeCopy = node.next;
            if (node.arb != null) {
                nodeCopy.arb = node.arb.next;
            }
            node = nodeCopy.next;
        }

        // 3. Adjust links to create newHead
        Node newHead = head.next;
        node = head;
        Node node2 = newHead;
        while (node != null) {
            node.next = node2.next;
            node = node.next;
            if (node != null) {
                node2.next = node.next;
            }
            node2 = node2.next;
        }
        return newHead;
    }
}
Java Program to clone the linked list with random link