Clone a linked list with next and random pointer

Time: O(n)

Space: O(1)

Intuition

Three passes: (1) interleave cloned nodes between original nodes, (2) set random pointers for cloned nodes, (3) separate the two lists.

Algorithm

1Pass 1: for each node N, insert clone N' after N: Nâ†’N'â†’N.next.
2Pass 2: for each original node N: N.next.random = N.random?.next.
3Pass 3: separate lists by fixing next pointers.

Common Pitfalls

•Pass 2 relies on the interleaved structure: original.random.next is the clone of original.random. Restore original list in pass 3.

Clone a linked list with next and random pointer.java

Java

// Approach: Three-pass: interleave cloned nodes, set random pointers, then separate the two lists.
// Time: O(n) Space: O(1)
class Node {
    int data;
    Node next, random;

    Node(int d) {
        data = d;
        next = random = null;

    }
}

class Solution {
    // Function to clone a linked list with next and random pointer.
    Node copyList(Node head) {
        Node temp = head;
        Node copy = new Node(0);
        Node point = copy;
        while (temp != null) {
            point.next = new Node(temp.data);
            temp = temp.next;
            point = point.next;
        }
        temp = head;
        point = copy.next;
        while (point != null) {
            if (temp.random != null) {

                Node randomPoint = copy.next;
                while (randomPoint != null) {
                    if (randomPoint.data == temp.random.data) {
                        point.random = randomPoint;
                        break;
                    }
                    randomPoint = randomPoint.next;
                }
            }
            point = point.next;
            temp = temp.next;

        }
        return copy.next;
    }
}

Was this solution helpful?