Clone Linked List with Random Pointers – Java Program

This Java program demonstrates how to clone a linked list where each node has a random pointer in addition to the next pointer. The random pointer can point to any node in the list or be null.

Program Structure

The program is structured into three main components:

1. ListNode Class: Defines the node structure for the linked list, including random pointers.
2. CloneLinkedList Class: Contains the method to clone the linked list with random pointers.
3. Main Class: Contains the main method to execute the program and test the cloning functionality.

Java Code

    /**
     * Definition for a singly-linked list with a random pointer.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode random;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next, ListNode random) { this.val = val; this.next = next; this.random = random; }
     * }
     */

    public class ListNode {
        int val;
        ListNode next;
        ListNode random;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next, ListNode random) { this.val = val; this.next = next; this.random = random; }
    }

    public class CloneLinkedList {
        /**
         * Clones a linked list with random pointers.
         * 
         * @param head The head of the original linked list.
         * @return The head of the cloned linked list.
         */
        public ListNode cloneList(ListNode head) {
            if (head == null) return null;
            
            // Step 1: Create a new copy of each node and insert it right after the original node
            ListNode current = head;
            while (current != null) {
                ListNode clone = new ListNode(current.val);
                clone.next = current.next;
                current.next = clone;
                current = clone.next;
            }
            
            // Step 2: Copy the random pointers
            current = head;
            while (current != null) {
                ListNode clone = current.next;
                if (current.random != null) {
                    clone.random = current.random.next;
                }
                current = clone.next;
            }
            
            // Step 3: Separate the cloned list from the original list
            ListNode dummy = new ListNode(0);
            ListNode copyCurrent = dummy;
            current = head;
            while (current != null) {
                copyCurrent.next = current.next;
                copyCurrent = copyCurrent.next;
                current.next = copyCurrent.next;
                current = current.next;
            }
            
            return dummy.next;
        }
    }

    public class Main {
        public static void main(String[] args) {
            // Create a linked list with random pointers for testing
            ListNode node1 = new ListNode(1);
            ListNode node2 = new ListNode(2);
            ListNode node3 = new ListNode(3);
            ListNode node4 = new ListNode(4);
            node1.next = node2;
            node2.next = node3;
            node3.next = node4;
            node1.random = node3;
            node2.random = node1;
            node3.random = node4;
            node4.random = node2;
            
            // Clone the linked list
            CloneLinkedList cloner = new CloneLinkedList();
            ListNode clonedHead = cloner.cloneList(node1);
            
            // Print the original and cloned lists
            System.out.println("Original linked list:");
            printList(node1);
            System.out.println("Cloned linked list:");
            printList(clonedHead);
        }
        
        // Helper method to print the linked list
        private static void printList(ListNode head) {
            ListNode current = head;
            while (current != null) {
                System.out.print("Value: " + current.val);
                if (current.random != null) {
                    System.out.print(", Random: " + current.random.val);
                } else {
                    System.out.print(", Random: null");
                }
                System.out.println();
                current = current.next;
            }
        }
    }
    

Explanation

ListNode Class: This class represents a node in the linked list. Each node contains an integer value, a reference to the next node, and a reference to a random node.

CloneLinkedList Class: This class contains the method cloneList that clones a linked list with random pointers. It performs the cloning in three steps: first, it inserts a copy of each node right after the original node; second, it copies the random pointers; and third, it separates the cloned list from the original list.

Main Class: This class is used for testing the cloning functionality. It creates a sample linked list with random pointers, clones it using the CloneLinkedList class, and prints both the original and cloned lists.