Copy Linked List with Random Pointer (Deep Copy) ใน C++

โจทย์

กำหนด Linked List ที่แต่ละโหนดมี next และ random pointer (ชี้ไปโหนดอื่นสุ่ม) สร้าง Deep Copy (โหนดใหม่ทุกตัว, random ชี้ไปโหนดใหม่ที่ตรงกัน)

ตัวอย่าง

Original:  5 → 6 → 3 → 4 → 2
Random:    ↓   ↓   ↓   ↓   ↓
           3   5   2   2   6

Deep Copy: 5'→ 6'→ 3'→ 4'→ 2'
Random:    ↓   ↓   ↓   ↓   ↓
           3'  5'  2'  2'  6'

แนวคิด: Interleaving Nodes (O(1) Space)

1. Interleave: สร้าง Copy ต่อท้ายโหนดเดิม: A→A'→B→B'→C→C'
2. Assign Random: copy->random = orig->random->next
3. Separate: แยกกลับเป็น 2 List

โค้ด C++

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int val;
    Node* next;
    Node* random;
    Node(int x) : val(x), next(nullptr), random(nullptr) {}
};

Node* copyRandomList(Node* head) {
    if (!head) return nullptr;
    
    // Step 1: Interleave copied nodes
    Node* curr = head;
    while (curr) {
        Node* copy = new Node(curr->val);
        copy->next = curr->next;
        curr->next = copy;
        curr = copy->next;
    }
    
    // Step 2: Assign random pointers
    curr = head;
    while (curr) {
        if (curr->random) {
            curr->next->random = curr->random->next;
        }
        curr = curr->next->next;
    }
    
    // Step 3: Separate lists
    curr = head;
    Node* copyHead = head->next;
    Node* copyCurr = copyHead;
    
    while (curr) {
        curr->next = copyCurr->next;
        curr = curr->next;
        if (curr) {
            copyCurr->next = curr->next;
            copyCurr = copyCurr->next;
        }
    }
    
    return copyHead;
}

// Alternative: Hash Map (O(n) Space, Easier)
Node* copyRandomListHash(Node* head) {
    if (!head) return nullptr;
    unordered_map map;
    
    // Pass 1: Create all nodes
    Node* curr = head;
    while (curr) {
        map[curr] = new Node(curr->val);
        curr = curr->next;
    }
    
    // Pass 2: Assign next and random
    curr = head;
    while (curr) {
        map[curr]->next = map[curr->next];
        map[curr]->random = map[curr->random];
        curr = curr->next;
    }
    
    return map[head];
}

void printList(Node* head) {
    while (head) {
        cout << head->val << "(" << (head->random ? to_string(head->random->val) : "null") << ") ";
        head = head->next;
    }
    cout << endl;
}

int main() {
    // Build: 5→6→3→4→2 with random pointers
    Node* n1 = new Node(5);
    Node* n2 = new Node(6);
    Node* n3 = new Node(3);
    Node* n4 = new Node(4);
    Node* n5 = new Node(2);
    
    n1->next = n2; n2->next = n3; n3->next = n4; n4->next = n5;
    n1->random = n3;      // 5 → 3
    n2->random = n1;      // 6 → 5
    n3->random = n5;      // 3 → 2
    n4->random = n5;      // 4 → 2
    n5->random = n2;      // 2 → 6
    
    cout << "Original: ";
    printList(n1);
    
    Node* copy = copyRandomList(n1);
    cout << "Copy:     ";
    printList(copy);
    
    // Verify deep copy
    cout << "Modify copy: ";
    copy->val = 99;
    cout << "Original head: " << n1->val << ", Copy head: " << copy->val << endl;
    
    return 0;
}

Complexity

ผลลัพธ์

Original: 5(3) 6(5) 3(2) 4(2) 2(6) 
Copy:     5(3) 6(5) 3(2) 4(2) 2(6) 
Modify copy: Original head: 5, Copy head: 99

สรุป

Copy List with Random Pointer: Interleaving Method (O(1) Space) หรือ Hash Map (O(n) Space) - LeetCode 138. Interleaving ต้องระวัง Edge Cases (NULL random, Single node)