Clone Linked List with Random Pointer in DSA Go

Mental Model

We want to make a new linked list that looks exactly like the original, including special random links that can point anywhere in the list.

Analogy: Imagine copying a chain of people holding hands, but some people also point randomly to others in the chain. We want to create a new chain where everyone holds hands and points exactly the same way, but with new people.

Original list:
1 -> 2 -> 3 -> null
Random pointers:
1.random -> 3
2.random -> 1
3.random -> 2

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3, with random pointers 1.random -> 3, 2.random -> 1, 3.random -> 2

Goal: Create a new list that copies both next and random pointers exactly, but with new nodes

Step 1: Insert copy nodes after each original node

1 -> [1'] -> 2 -> [2'] -> 3 -> [3'] -> null

Why: This helps link original and copy nodes side by side for easy random pointer assignment

Step 2: Assign random pointers for copy nodes using original nodes' random pointers

1.random -> 3, 1'.random -> 3'
2.random -> 1, 2'.random -> 1'
3.random -> 2, 3'.random -> 2'

Why: Copy nodes get random pointers by looking at original node's random and moving one step to the copy

Step 3: Separate the combined list into original and copied lists

Original: 1 -> 2 -> 3 -> null
Copy: 1' -> 2' -> 3' -> null

Why: We restore original list and extract the cloned list with correct next and random pointers

Result:

Cloned list:
1' -> 2' -> 3' -> null
Random pointers:
1'.random -> 3'
2'.random -> 1'
3'.random -> 2'

Annotated Code

DSA Go

package main

import "fmt"

// Node defines a linked list node with next and random pointers
type Node struct {
	Val    int
	Next   *Node
	Random *Node
}

// cloneLinkedList clones a linked list with random pointers
func cloneLinkedList(head *Node) *Node {
	if head == nil {
		return nil
	}

	// Step 1: Insert copy nodes after original nodes
	curr := head
	for curr != nil {
		copy := &Node{Val: curr.Val}
		copy.Next = curr.Next
		curr.Next = copy
		curr = copy.Next
	}

	// Step 2: Assign random pointers for copy nodes
	curr = head
	for curr != nil {
		if curr.Random != nil {
			curr.Next.Random = curr.Random.Next
		}
		curr = curr.Next.Next
	}

	// Step 3: Separate original and copy lists
	curr = head
	copyHead := head.Next
	for curr != nil {
		copy := curr.Next
		curr.Next = copy.Next
		if copy.Next != nil {
			copy.Next = copy.Next.Next
		}
		curr = curr.Next
	}

	return copyHead
}

// printList prints the list showing values and random pointers
func printList(head *Node) {
	curr := head
	for curr != nil {
		randomVal := "null"
		if curr.Random != nil {
			randomVal = fmt.Sprintf("%d", curr.Random.Val)
		}
		fmt.Printf("%d(random->%s) -> ", curr.Val, randomVal)
		curr = curr.Next
	}
	fmt.Println("null")
}

func main() {
	// Create original list 1->2->3
	n1 := &Node{Val: 1}
	n2 := &Node{Val: 2}
	n3 := &Node{Val: 3}
	n1.Next = n2
	n2.Next = n3

	// Setup random pointers
	n1.Random = n3
	n2.Random = n1
	n3.Random = n2

	fmt.Println("Original list:")
	printList(n1)

	cloned := cloneLinkedList(n1)
	fmt.Println("Cloned list:")
	printList(cloned)
}

for curr != nil { copy := &Node{Val: curr.Val} copy.Next = curr.Next curr.Next = copy curr = copy.Next }

Insert copy nodes after each original node to link originals and copies side by side

for curr != nil { if curr.Random != nil { curr.Next.Random = curr.Random.Next } curr = curr.Next.Next }

Assign random pointers for copy nodes by using original nodes' random pointers

for curr != nil { copy := curr.Next curr.Next = copy.Next if copy.Next != nil { copy.Next = copy.Next.Next } curr = curr.Next }

Separate the combined list into original and cloned lists restoring original next pointers

Output

Original list:

1(random->3) -> 2(random->1) -> 3(random->2) -> null

Cloned list:

1(random->3) -> 2(random->1) -> 3(random->2) -> null

Complexity Analysis

Time: O(n) because we traverse the list a few times but each node is visited a constant number of times

Space: O(1) because we create new nodes but do not use extra data structures proportional to n

vs Alternative: Compared to using a hash map to store original-to-copy mapping which uses O(n) extra space, this approach uses no extra space besides new nodes

Edge Cases

empty list

returns nil without error

DSA Go

if head == nil {
	return nil
}

list with one node and random pointer to itself

correctly clones node and random pointer points to cloned node itself

DSA Go

curr.Next.Random = curr.Random.Next

random pointers are nil

copy nodes have nil random pointers as expected

DSA Go

if curr.Random != nil {
	curr.Next.Random = curr.Random.Next
}

When to Use This Pattern

When you see a linked list with random pointers and need to clone it exactly, use the interleaving nodes pattern to assign random pointers without extra space.

Common Mistakes

Mistake: Not inserting copy nodes between original nodes first, making random pointer assignment complicated
Fix: First insert copy nodes right after originals to link them side by side

Mistake: Assigning random pointers of copy nodes incorrectly by not referencing the copy of the random target
Fix: Set copy's random to original.random.next to get the copy node

Mistake: Not restoring original list's next pointers after separation
Fix: Restore original next pointers while separating the combined list

Summary

Creates a deep copy of a linked list with next and random pointers.

Use when you need an exact clone of a complex linked list with random connections.

Interleave copied nodes with original nodes to assign random pointers easily without extra space.

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