Clone a Linked List with Random Pointers in Go

Program Code

package main

import "fmt"

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

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

    // Step 1: Create a copy of each node and insert it next to the original node
    current := head
    for current != nil {
        copyNode := &Node{Val: current.Val}
        copyNode.Next = current.Next
        current.Next = copyNode
        current = copyNode.Next
    }

    // Step 2: Set the random pointers for the copied nodes
    current = head
    while current != nil {
        copyNode := current.Next
        if current.Random != nil {
            copyNode.Random = current.Random.Next
        }
        current = copyNode.Next
    }

    // Step 3: Separate the original list from the copied list
    original := head
    copy := head.Next
    copyHead := copy
    for original != nil {
        original.Next = original.Next.Next
        if copy.Next != nil {
            copy.Next = copy.Next.Next
        }
        original = original.Next
        copy = copy.Next
    }

    return copyHead
}

// Helper function to print the linked list
func printList(head *Node) {
    for head != nil {
        fmt.Printf("Value: %d, Random: %v -> ", head.Val, head.Random.Val)
        head = head.Next
    }
    fmt.Println("nil")
}

// Main function to test the cloneList function
func main() {
    // Create a linked list with random pointers
    // List: 1 -> 2 -> 3
    // Random pointers: 1->3, 2->1, 3->2

    // Create nodes
    node1 := &Node{Val: 1}
    node2 := &Node{Val: 2}
    node3 := &Node{Val: 3}

    // Setup next pointers
    node1.Next = node2
    node2.Next = node3

    // Setup random pointers
    node1.Random = node3
    node2.Random = node1
    node3.Random = node2

    fmt.Print("Original List: ")
    printList(node1)

    // Clone the linked list
    cloned := cloneList(node1)

    fmt.Print("Cloned List: ")
    printList(cloned)
}
    

Explanation

The Go program is designed to clone a linked list where each node has a random pointer in addition to the next pointer. Here is a detailed explanation of the program structure:

1. Node Definition

The Node struct defines a node in the linked list with:

• Val: The value of the node.
• Next: A pointer to the next node in the list.
• Random: A pointer to a random node in the list.

2. cloneList Function

The cloneList function clones the linked list with random pointers:

• Step 1: Create a copy of each node and insert it immediately after the original node.
• Step 2: Set the random pointers for the copied nodes using the random pointers of the original nodes.
• Step 3: Separate the original list from the copied list. Restore the next pointers of the original list and extract the cloned list from the interleaved nodes.

3. printList Function

The printList function prints the values and random pointer references of the linked list nodes for demonstration purposes.

4. Main Function

The main function demonstrates the usage of the cloneList function:

• Creates a sample linked list with random pointers.
• Prints the original linked list.
• Clones the list using cloneList and prints the cloned list.