Clone a linked list with next and random pointer

Time: O(n)

Space: O(1)

Problem Overview

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

See our study guide for structured GFG and LeetCode practice.

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?