Clone Linked List with Random Pointer in DSA Go - Build from Scratch

Clone Linked List with Random Pointer

📖 Scenario: Imagine you have a special linked list where each node has two pointers: one points to the next node, and another points to any random node in the list or null. You want to make a perfect copy of this list, including the random connections.

🎯 Goal: Build a Go program that clones a linked list with random pointers. The clone should have new nodes with the same values and the same next and random pointer structure as the original.

📋 What You'll Learn

Define a Node struct with Val, Next, and Random fields

Create an initial linked list with 3 nodes and specific random pointers

Add a helper map to track original to cloned nodes

Implement the cloning logic that copies nodes and sets next and random pointers correctly

Print the cloned list nodes showing their values and the values of their random pointers

💡 Why This Matters

🌍 Real World

Cloning complex linked data structures is useful in applications like undo-redo systems, copying game states, or duplicating complex graphs with random connections.

💼 Career

Understanding how to clone linked structures with random pointers is important for software engineers working on low-level data manipulation, memory management, and complex data structure algorithms.

1

Create the original linked list with random pointers

Define a Node struct with Val int, Next *Node, and Random *Node. Then create three nodes named node1, node2, and node3 with values 1, 2, and 3 respectively. Link them so that node1.Next = node2 and node2.Next = node3. Set random pointers: node1.Random = node3, node2.Random = node1, and node3.Random = node2. Finally, create a variable head pointing to node1.

DSA Go

// Define Node struct and create linked list with random pointers
// Your code here

Hint

Start by defining the Node struct with the three fields. Then create three nodes with values 1, 2, and 3. Connect their Next and Random pointers as described. Finally, set head to the first node.

2

Create a map to track original to cloned nodes

Add a variable nodeMap of type map[*Node]*Node and initialize it as an empty map. This map will help link original nodes to their clones.

DSA Go

package main

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

func main() {
    node1 := &Node{Val: 1}
    node2 := &Node{Val: 2}
    node3 := &Node{Val: 3}

    node1.Next = node2
    node2.Next = node3

    node1.Random = node3
    node2.Random = node1
    node3.Random = node2

    head := node1

    nodeMap := make(map[*Node]*Node)
    // Your code here
}

Hint

Use make(map[*Node]*Node) to create an empty map that links original nodes to their clones.

3

Clone nodes and set next and random pointers

Write a for loop using curr := head and iterate while curr != nil. Inside the loop, create a clone node with Val: curr.Val and store it in nodeMap[curr]. Then move curr to curr.Next. After this loop, reset curr = head and loop again. This time, set nodeMap[curr].Next = nodeMap[curr.Next] and nodeMap[curr].Random = nodeMap[curr.Random] if they exist. Move curr to curr.Next each iteration. Finally, create a variable clonedHead equal to nodeMap[head].

DSA Go

package main

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

func main() {
    node1 := &Node{Val: 1}
    node2 := &Node{Val: 2}
    node3 := &Node{Val: 3}

    node1.Next = node2
    node2.Next = node3

    node1.Random = node3
    node2.Random = node1
    node3.Random = node2

    head := node1

    nodeMap := make(map[*Node]*Node)

    // Clone nodes
    curr := head
    for curr != nil {
        // Your code here
    }

    // Set next and random pointers
    curr = head
    for curr != nil {
        // Your code here
    }

    // Create clonedHead
    // Your code here
}

Hint

First loop: create new nodes and store in map. Second loop: assign Next and Random pointers using the map. Finally, get clonedHead from the map.

4

Print the cloned list showing values and random pointers

Write a for loop with curr := clonedHead iterating while curr != nil. Inside the loop, print the current node's value and the value of its random pointer or nil if random is nil. Use fmt.Printf("Node Val: %d, Random Val: %v\n", curr.Val, randomVal) where randomVal is curr.Random.Val or "nil". Move curr to curr.Next. Import fmt at the top.

DSA Go

package main

import "fmt"

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

func main() {
    node1 := &Node{Val: 1}
    node2 := &Node{Val: 2}
    node3 := &Node{Val: 3}

    node1.Next = node2
    node2.Next = node3

    node1.Random = node3
    node2.Random = node1
    node3.Random = node2

    head := node1

    nodeMap := make(map[*Node]*Node)

    // Clone nodes
    curr := head
    for curr != nil {
        nodeMap[curr] = &Node{Val: curr.Val}
        curr = curr.Next
    }

    // Set next and random pointers
    curr = head
    for curr != nil {
        if curr.Next != nil {
            nodeMap[curr].Next = nodeMap[curr.Next]
        }
        if curr.Random != nil {
            nodeMap[curr].Random = nodeMap[curr.Random]
        }
        curr = curr.Next
    }

    clonedHead := nodeMap[head]

    // Print cloned list
    curr = clonedHead
    for curr != nil {
        // Your code here
    }
}

Hint

Loop through clonedHead. For each node, check if Random is nil. Print the node's value and the random node's value or "nil" if none.

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