Clone Linked List with Random Pointer in DSA Go - Execution Trace

Concept Flow - Clone Linked List with Random Pointer

Start at head of original list

↓

Create new node for each original node

↓

Insert new node just after original node

↓

Assign random pointers for new nodes

↓

Separate original and cloned lists

↓

Return head of cloned list

We first create new nodes and insert them after original nodes, then assign random pointers for clones, and finally separate the two lists.

Execution Sample

DSA Go

func cloneList(head *Node) *Node {
  // Step 1: Insert cloned nodes
  // Step 2: Assign random pointers
  // Step 3: Separate lists
}

This code clones a linked list with random pointers by interleaving cloned nodes, setting random pointers, and then separating the lists.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Start at head	A->B->C->null	head points to A	A(random)->B(random)->C(random)->null
2	Create clone of A and insert after A	A->A'->B->C->null	A.next = A', A'.next = B	A->A'->B->C->null
3	Create clone of B and insert after B	A->A'->B->B'->C->null	B.next = B', B'.next = C	A->A'->B->B'->C->null
4	Create clone of C and insert after C	A->A'->B->B'->C->C'->null	C.next = C', C'.next = null	A->A'->B->B'->C->C'->null
5	Assign random pointer for A'	No change in nodes	A'.random = A.random.next (clone of A.random)	A'.random points to clone of A.random
6	Assign random pointer for B'	No change in nodes	B'.random = B.random.next	B'.random points to clone of B.random
7	Assign random pointer for C'	No change in nodes	C'.random = C.random.next	C'.random points to clone of C.random
8	Separate original and cloned lists	Original: A->B->C->null Clone: A'->B'->C'->null	Restore original next pointers, set clone next pointers	Two separate lists with correct next and random pointers
9	Return head of cloned list	No change	Return A'	Cloned list head returned
10	End	No change	Process complete	Cloned list fully constructed

💡 All nodes cloned, random pointers assigned, and lists separated.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 7	After Step 8	Final
head	A	A	A	A	A	A
current	A	A'	C'	C'	null	null
clone_head	null	null	null	null	A'	A'
A.next	B	A'	A'	A'	B	B
A'.next	null	B	B	B	B'	B'
A'.random	null	null	null	clone of A.random	clone of A.random	clone of A.random
B'.random	null	null	null	clone of B.random	clone of B.random	clone of B.random
C'.random	null	null	null	clone of C.random	clone of C.random	clone of C.random

Key Moments - 3 Insights

Why do we insert cloned nodes immediately after original nodes?

Inserting clones after originals allows easy access to the clone of any node via original.next, which helps assign random pointers correctly as shown in steps 2-7 of the execution_table.

How do we assign the random pointer of a cloned node?

We assign clone.random = original.random.next because original.random.next points to the clone of the original node's random target, as explained in steps 5-7.

Why do we need to separate the lists at the end?

Because during cloning, original and cloned nodes are interleaved, we must restore the original list and extract the cloned list separately, as done in step 8.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the visual state of the list?

A A->A'->B->B'->C->C'->null

B A->B->C->null

C A'->B'->C'->null

D A->B->C->C'->null

💡 Hint

Check the 'Visual State' column at step 4 in the execution_table.

At which step do we assign the random pointer for B' clone?

A Step 3

B Step 8

C Step 6

D Step 2

💡 Hint

Look at the 'Operation' column in execution_table for random pointer assignments.

If we skip separating the lists at step 8, what happens to the final cloned list?

A It will be empty

B It will be interleaved with original nodes

C It will have no random pointers

D It will be reversed

💡 Hint

Refer to the 'Pointer Changes' and 'Visual State' columns at step 8.

Concept Snapshot

Clone Linked List with Random Pointer:
1. Insert cloned nodes after originals.
2. Assign cloned nodes' random pointers using original.random.next.
3. Separate the interleaved lists to restore original and get clone.
4. Return head of cloned list.
This method avoids extra space for mapping nodes.

Full Transcript

To clone a linked list with random pointers, we first create a clone node for each original node and insert it immediately after the original node. This interleaving helps us assign the random pointers of cloned nodes by using the original node's random pointer's next node, which is the clone. After setting all random pointers, we separate the combined list into the original list and the cloned list. Finally, we return the head of the cloned list. This approach efficiently clones the list without extra space for a hash map.

Practice

1. What is the main challenge when cloning a linked list with a random pointer?

easy

A. Reversing the linked list during cloning

B. Only copying the next pointers

C. Ignoring the random pointers

D. Copying both the next and random pointers correctly

Solution

1. Step 1: Understand the structure of the linked list

   The linked list has two pointers per node: next and random. Both need to be copied to clone the list correctly.

2. Step 2: Identify the cloning challenge

   Copying next pointers is straightforward, but random pointers can point anywhere, so they must be handled carefully to maintain correct references.

3. Final Answer:

   Copying both the next and random pointers correctly -> Option D

4. Quick Check:

   Cloning requires both pointers copied correctly [OK]

Hint: Remember: random pointers can point anywhere, copy carefully [OK]

Common Mistakes:

• Copying only next pointers and ignoring random
• Assuming random pointers follow next pointers
• Not handling null random pointers

2. Which Go syntax correctly declares a struct node with next and random pointers for cloning a linked list?

easy

A. type Node struct { Val int; Next Node; Random Node }

B. type Node struct { Val int; Next *Node; Random *Node }

C. type Node struct { Val int; Next *int; Random *int }

D. type Node struct { Val int; Next *Node; Random int }

Solution

1. Step 1: Understand pointer usage in Go structs

   Next and Random should be pointers to Node to link nodes properly, so use *Node type.

2. Step 2: Check each option for correct pointer types

   type Node struct { Val int; Next *Node; Random *Node } uses *Node for both Next and Random, which is correct. Others use wrong types or non-pointers.

3. Final Answer:

   type Node struct { Val int; Next *Node; Random *Node } -> Option B

4. Quick Check:

   Use pointers for linked nodes in Go structs [OK]

Hint: Use *Node type for next and random pointers in struct [OK]

Common Mistakes:

• Using value type instead of pointer for next/random
• Using wrong pointer types like *int
• Mixing pointer and non-pointer types incorrectly

3. Given the following Go code snippet for cloning a linked list with random pointers, what will be the output of printing the cloned list values in order?

type Node struct {
    Val    int
    Next   *Node
    Random *Node
}

func cloneList(head *Node) *Node {
    if head == nil {
        return nil
    }
    // Step 1: Insert cloned nodes
    curr := head
    for curr != nil {
        newNode := &Node{Val: curr.Val}
        newNode.Next = curr.Next
        curr.Next = newNode
        curr = newNode.Next
    }
    // Step 2: Copy random pointers
    curr = head
    for curr != nil {
        if curr.Random != nil {
            curr.Next.Random = curr.Random.Next
        }
        curr = curr.Next.Next
    }
    // Step 3: Separate cloned list
    curr = head
    cloneHead := head.Next
    cloneCurr := cloneHead
    for curr != nil {
        curr.Next = curr.Next.Next
        if cloneCurr.Next != nil {
            cloneCurr.Next = cloneCurr.Next.Next
        }
        curr = curr.Next
        cloneCurr = cloneCurr.Next
    }
    return cloneHead
}

// Original list: 1 -> 2 -> 3 -> nil
// Random pointers: 1.random = 3, 2.random = 1, 3.random = 2

func main() {
    n3 := &Node{Val: 3}
    n2 := &Node{Val: 2, Next: n3}
    n1 := &Node{Val: 1, Next: n2}
    n1.Random = n3
    n2.Random = n1
    n3.Random = n2

    cloned := cloneList(n1)
    curr := cloned
    for curr != nil {
        fmt.Print(curr.Val)
        if curr.Next != nil {
            fmt.Print(" -> ")
        }
        curr = curr.Next
    }
    fmt.Println(" -> nil")
}

medium

A. 1 -> 2 -> 3 -> nil

B. 3 -> 2 -> 1 -> nil

C. 1 -> 3 -> 2 -> nil

D. nil

Solution

1. Step 1: Understand cloning steps

   The code clones nodes by inserting new nodes after originals, copies random pointers, then separates cloned list.

2. Step 2: Trace the cloned list values

   Original list is 1->2->3. Cloned list copies values in same order: 1->2->3.

3. Final Answer:

   1 -> 2 -> 3 -> nil -> Option A

4. Quick Check:

   Cloned list values match original order [OK]

Hint: Cloned list keeps original order of nodes [OK]

Common Mistakes:

• Assuming cloned list reverses order
• Confusing random pointer order with next pointer order
• Not separating cloned list properly

4. Identify the bug in this Go function that attempts to clone a linked list with random pointers:

func cloneList(head *Node) *Node {
    if head == nil {
        return nil
    }
    curr := head
    for curr != nil {
        newNode := &Node{Val: curr.Val}
        newNode.Next = curr.Next
        curr.Next = newNode
        curr = curr.Next
    }
    curr = head
    for curr != nil {
        if curr.Random != nil {
            curr.Next.Random = curr.Random.Next
        }
        curr = curr.Next.Next
    }
    curr = head
    cloneHead := head.Next
    cloneCurr := cloneHead
    for curr != nil {
        curr.Next = curr.Next.Next
        if cloneCurr.Next != nil {
            cloneCurr.Next = cloneCurr.Next.Next
        }
        curr = curr.Next
        cloneCurr = cloneCurr.Next
    }
    return cloneHead
}

medium

A. In the first loop, curr = curr.Next should be curr = curr.Next.Next

B. Random pointers are not copied correctly

C. The cloned list is not separated from the original

D. The function does not handle empty lists

Solution

1. Step 1: Analyze the first loop for inserting cloned nodes

   After inserting newNode, curr should move two steps to skip the new node and reach next original node.

2. Step 2: Identify incorrect pointer update

   The code uses curr = curr.Next, which moves to the new node again, causing an infinite loop or incorrect behavior.

3. Final Answer:

   In the first loop, curr = curr.Next should be curr = curr.Next.Next -> Option A

4. Quick Check:

   Move curr two steps after inserting clone [OK]

Hint: After inserting clone, skip it by moving curr two steps [OK]

Common Mistakes:

• Moving curr only one step causes infinite loop
• Not updating random pointers properly
• Forgetting to separate cloned list

5. You want to clone a linked list with random pointers but also reverse the cloned list. Which approach correctly combines cloning and reversing in Go? A) Clone the list first, then reverse the cloned list by changing next pointers. B) Reverse the original list first, then clone it. C) Clone the list and reverse random pointers instead of next pointers. D) Clone the list and keep the order same, reversing is not possible with random pointers.

hard

A. Clone the list and reverse random pointers instead of next pointers.

B. Reverse the original list first, then clone it.

C. Clone the list first, then reverse the cloned list by changing next pointers.

D. Clone the list and keep the order same, reversing is not possible with random pointers.

Solution

1. Step 1: Understand cloning and reversing separately

   Cloning creates a copy with correct next and random pointers. Reversing changes next pointers order.

2. Step 2: Combine cloning and reversing correctly

   Clone first to preserve random pointers, then reverse cloned list's next pointers without affecting random pointers.

3. Final Answer:

   Clone the list first, then reverse the cloned list by changing next pointers. -> Option C

4. Quick Check:

   Clone then reverse next pointers to keep random intact [OK]

Hint: Clone first, then reverse next pointers only [OK]

Common Mistakes:

• Reversing original list breaks random pointer references
• Reversing random pointers instead of next pointers
• Assuming reversing is impossible with random pointers