Copy List with Random Pointer: khi con trỏ next chưa đủ

Bài toán trông rất gần với copy linked list thông thường — duyệt, clone từng node, nối next. Cách đó ổn cho đến khi bạn gặp random. Con trỏ này có thể nhắm vào bất kỳ node nào trong danh sách: node ba vị trí phía trước, ba vị trí phía sau, thậm chí chính nó. Khi bạn đang clone node B và cần gán B'.random, node mà B.random trỏ đến có thể chưa được clone.

Đó mới là vấn đề thực sự. Làm sao bạn gán một con trỏ đến bản sao chưa tồn tại?

Danh sách từ Example 1: [[7,null],[13,0],[11,4],[10,2],[1,0]]. Mỗi cạnh next đi về bên phải. Các cạnh random tỏa ra tự do — node 1 trỏ ngược về node 0, node 4 trỏ về node 2. Một single-pass clone ngây thơ sẽ vỡ ngay khi cố gán random đến node chưa được tạo.

Đề bài

Cho một linked list mà mỗi node chứa một số nguyên và hai con trỏ — next trỏ đến node tiếp theo và random trỏ đến bất kỳ node nào trong danh sách (hoặc null) — hãy tạo một deep copy hoàn chỉnh sao cho không có con trỏ nào trong danh sách mới trỏ về node của danh sách gốc. Xem đề gốc: LeetCode 138.

Ràng buộc:
- 0 <= n <= 1000
- -10^4 <= Node.val <= 10^4
- Node.random là null hoặc trỏ đến một node trong danh sách.

Constraints nói gì

0 <= n <= 1000 và -10^4 <= Node.val <= 10^4.

n tối đa 1000 nghĩa là O(n) là target duy nhất hợp lý. Không có mẹo O(n log n) nào cần với và cũng không có O(n^2) brute force nào cám dỗ ở quy mô này. Constraint đang nói với bạn một cách lặng lẽ: một hoặc hai lần duyệt danh sách là đủ.

Dải giá trị [-10^4, 10^4] không liên quan đến thuật toán. Giá trị được copy nguyên — bạn không bao giờ sort hay tìm kiếm theo chúng. Điều quan trọng là bạn không thể dùng giá trị làm định danh. Hai node có cùng giá trị 3 là hai object riêng biệt — bản sao của node đầu tiên không được bí mật trỏ vào bản sao của node thứ hai.

Node.random hoặc null hoặc trỏ đến một node trong cùng danh sách. Nó không bao giờ thoát ra ngoài. Điều đó quan trọng: mọi target của random pointer đều đã có vị trí trong danh sách, và bạn có thể pre-build tất cả bản sao trước khi nối bất kỳ con trỏ nào.

Trường hợp khó nhất về mặt cấu trúc: một node có random trỏ chính vào nó. Thuật toán phải xử lý được điều đó mà không bị lỗi.

Approach 1: hash map — xây index bản sao trước

Cách sạch nhất để giải quyết vấn đề back-reference là build tất cả bản sao trước khi nối bất kỳ con trỏ nào. Một hash map với key là node gốc và value là clone tương ứng cho bạn tra cứu O(1) khi cần dịch old.random -> new.random.

Hai lần duyệt: lần đầu tạo tất cả node, lần hai nối next và random.

class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
 
class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head:
            return None
 
        old_to_new = {}
 
        # Lần duyệt đầu: tạo tất cả clone, chưa nối con trỏ
        current = head
        while current:
            old_to_new[current] = Node(current.val)
            current = current.next
 
        # Lần duyệt hai: nối next và random qua hash map
        current = head
        while current:
            clone = old_to_new[current]
            if current.next:
                clone.next = old_to_new[current.next]
            if current.random:
                clone.random = old_to_new[current.random]
            current = current.next
 
        return old_to_new[head]

public class Solution {
    public Node CopyRandomList(Node head) {
        if (head == null) return null;
 
        var oldToNew = new Dictionary<Node, Node>();
 
        // Lần duyệt đầu: tạo tất cả clone
        Node current = head;
        while (current != null) {
            oldToNew[current] = new Node(current.val);
            current = current.next;
        }
 
        // Lần duyệt hai: nối next và random
        current = head;
        while (current != null) {
            Node clone = oldToNew[current];
            if (current.next != null)
                clone.next = oldToNew[current.next];
            if (current.random != null)
                clone.random = oldToNew[current.random];
            current = current.next;
        }
 
        return oldToNew[head];
    }
}

Trace tay qua Example 1

Danh sách: 7 -> 13 -> 11 -> 10 -> 1. Gọi các node gốc là A, B, C, D, E.

Lần duyệt đầu — sau vòng while:

old_to_new = {
    A(7):  A'(7),
    B(13): B'(13),
    C(11): C'(11),
    D(10): D'(10),
    E(1):  E'(1)
}

Chưa có next hay random nào được gán. Mỗi clone là một node biệt lập.

Lần duyệt hai — nối từng node:

current = A(7):
  A'.next   = old_to_new[B] = B'(13)    ✓
  A'.random = null                        ✓

current = B(13):
  B'.next   = old_to_new[C] = C'(11)    ✓
  B'.random = old_to_new[A] = A'(7)     ✓  (random index 0 -> A)

current = C(11):
  C'.next   = old_to_new[D] = D'(10)    ✓
  C'.random = old_to_new[E] = E'(1)     ✓  (random index 4 -> E)

current = D(10):
  D'.next   = old_to_new[E] = E'(1)     ✓
  D'.random = old_to_new[C] = C'(11)    ✓  (random index 2 -> C)

current = E(1):
  E'.next   = null                        ✓
  E'.random = old_to_new[A] = A'(7)     ✓  (random index 0 -> A)

Trả về old_to_new[head] = A'. Danh sách clone được nối đầy đủ. Không có node nào trong danh sách gốc có thể truy cập từ bản sao.

Complexity: Time O(n) — hai lần duyệt, mỗi lần O(n). Space O(n) — hash map giữ một entry cho mỗi node.

Approach 2: interweaving — clone in-place, O(1) auxiliary space

Hash map hoạt động được vì nó lưu mapping từ gốc sang clone. Nhưng mapping đó chỉ trả lời một câu hỏi duy nhất: "với node gốc này, clone tương ứng là gì?" Kỹ thuật interweaving mã hóa câu trả lời đó trực tiếp vào cấu trúc danh sách, không cần cấu trúc dữ liệu riêng.

Ý tưởng: sau khi clone node A, chèn A' ngay phía sau A trong danh sách. Kết quả là:

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

Bây giờ clone của bất kỳ node X nào chính là X.next. Đó là O(1) lookup.

Gán random cho các clone trở thành: clone.random = original.random.next. Vì original.random.next là clone của bất kỳ node nào mà original.random trỏ đến.

Ba lần duyệt tổng cộng.

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head:
            return None
 
        # Bước 1: xen kẽ các clone vào danh sách gốc
        current = head
        while current:
            clone = Node(current.val)
            clone.next = current.next
            current.next = clone
            current = clone.next   # nhảy đến node gốc tiếp theo
 
        # Bước 2: gán random cho các clone
        current = head
        while current:
            clone = current.next
            if current.random:
                clone.random = current.random.next
            current = clone.next
 
        # Bước 3: tách danh sách clone, phục hồi danh sách gốc
        dummy = Node(0)
        new_cur = dummy
        current = head
 
        while current:
            clone = current.next
            current.next = clone.next   # phục hồi danh sách gốc
            new_cur.next = clone
            new_cur = clone
            current = current.next
 
        return dummy.next

public class Solution {
    public Node CopyRandomList(Node head) {
        if (head == null) return null;
 
        // Bước 1: xen kẽ các clone
        Node current = head;
        while (current != null) {
            Node clone = new Node(current.val);
            clone.next = current.next;
            current.next = clone;
            current = clone.next;
        }
 
        // Bước 2: gán random cho các clone
        current = head;
        while (current != null) {
            Node clone = current.next;
            if (current.random != null)
                clone.random = current.random.next;
            current = clone.next;
        }
 
        // Bước 3: tách hai danh sách
        Node dummy = new Node(0);
        Node newCur = dummy;
        current = head;
 
        while (current != null) {
            Node clone = current.next;
            current.next = clone.next;
            newCur.next = clone;
            newCur = clone;
            current = current.next;
        }
 
        return dummy.next;
    }
}

Trace tay qua Example 2

Danh sách: 1 -> 2. Node 0 (val=1) có random -> index 1. Node 1 (val=2) có random -> index 1 (chính nó).

Bước 1 — interweave:

Ban đầu:  1 -> 2 -> null

Sau clone node 1(val=1):
  1 -> 1' -> 2 -> null

Sau clone node 2(val=2):
  1 -> 1' -> 2 -> 2' -> null

Bước 2 — gán random cho clone:

current = node 1(val=1):
  clone = node 1'
  current.random = node 2(val=2)
  clone.random   = current.random.next = node 2' ✓

current = node 2(val=2):
  clone = node 2'
  current.random = node 2(val=2) [chính nó]
  clone.random   = current.random.next = node 2' [chính nó] ✓

random tự tham chiếu được giải quyết đúng: node 2'.random trỏ đến node 2', không phải node 2 gốc.

Bước 3 — tách:

Rút 1', rút 2'.
Danh sách gốc được phục hồi: 1 -> 2 -> null
Danh sách clone:              1' -> 2' -> null

Trả về 1'.

Complexity: Time O(n) — ba lần duyệt, mỗi lần O(n). Space O(1) auxiliary — không có hash map, chỉ thao tác con trỏ. Danh sách output O(n) là bắt buộc theo yêu cầu bài.

Các edge case

Danh sách rỗng (head = null): Cả hai approach trả về null ở dòng đầu tiên. Không có gì thực thi thêm.

Một node, random là null: Bước 1 tạo một clone. Bước 2 thấy current.random là null, bỏ qua. Bước 3 rút clone duy nhất. Sạch.

Một node, random trỏ chính vào nó: Trường hợp self-referencing trong trace ở trên. Interweaving xử lý được: clone.random = current.random.next, và current.random.next chính là clone. Hash map xử lý còn đơn giản hơn: old_to_new[current.random] = old_to_new[current] = clone.

Tất cả random pointer là null: Không cần xử lý đặc biệt. Câu lệnh if current.random: trả về false mọi lần.

Tất cả node có cùng giá trị: Giá trị không được dùng làm định danh ở đâu cả. Hash map key theo object identity (địa chỉ bộ nhớ), không phải giá trị. Interweaving không bao giờ dùng giá trị cho logic. Duplicate không phải vấn đề.

Random pointer tạo chuỗi dài trỏ ngược: Chẳng hạn node 4 trỏ về node 0, node 3 cũng trỏ về node 0. Trong hash map, khi lần duyệt hai đến node 4, node 0 và clone của nó đã có trong map — back reference được giải quyết sạch vì tất cả clone được build ở lần duyệt một. Trong interweaving, back reference cũng hoạt động tương tự: current.random.next nhìn vào node ngay sau target gốc, luôn là clone của nó sau bước 1.

Pattern ẩn đằng sau cả hai approach

Vấn đề căn bản là forward reference dưới một con trỏ không tuần tự. Bạn không thể giải quyết random trong lúc đi qua vì nó có thể trỏ đến node chưa được nhìn thấy.

Cả hai approach giải quyết điều này bằng cách tách bài toán thành các giai đoạn. Bạn không bao giờ cố làm mọi thứ trong một lần duyệt. Giai đoạn một: đảm bảo mọi node gốc đều có clone tương ứng đang tồn tại. Giai đoạn hai: nối các con trỏ, lúc này mọi lookup target đã sẵn sàng.

Hash map làm cho cấu trúc hai giai đoạn trở nên tường minh. Interweaving làm cho nó trở thành cấu trúc — clone nằm ngay cạnh gốc của nó trong danh sách, nên "tra cứu clone" trở thành "bước thêm một next."

Pattern tách giai đoạn này xuất hiện trong các bài clone graph nói chung. LeetCode 133 (Clone Graph) dùng logic y hệt: trước tiên build node cho mọi đỉnh, sau đó nối các cạnh. Random pointer ở đây tương đương với một cạnh đồ thị tổng quát.

Nên viết approach nào

Tôi chọn phiên bản hash map trong phỏng vấn hoặc môi trường production trừ khi memory là constraint tường minh. Ý định rõ ràng ngay lập tức: build map, sau đó nối con trỏ qua map. Hai vòng while, năm dòng logic mỗi vòng. Bất kỳ ai bảo trì code này đều hiểu trong 30 giây.

Interweaving clever và thực sự đạt O(1) auxiliary space. Nhưng nó mutates danh sách input trong suốt thời gian thuật toán chạy. Nếu có gì sai ở bước 2 hoặc 3 — một exception, một bug, một caller giả định danh sách gốc không bị thay đổi — bạn đã corrupt input. Trong production linked list nằm trong shared memory hoặc được truy cập đồng thời, đó là rủi ro thực sự. Hash map không bao giờ đụng đến danh sách gốc.

Còn có một chi phí về readability: interweaving yêu cầu bạn phải nhớ rằng "sau bước 1, node.next không còn là node kế tiếp trong danh sách gốc — nó là clone." Sự gián tiếp đó không hiển nhiên và cần comment. Hash map không cần giải thích như vậy.

Nếu người phỏng vấn yêu cầu O(1) space, interweaving là câu trả lời đúng. Ngược lại, tôi sẽ viết phiên bản hash map, giải thích rõ trade-off, và đề cập đến O(1) alternative.

Bảng so sánh

Cả hai đều O(n) time. Sự khác biệt space là trade-off duy nhất thực sự, và mức độ quan trọng phụ thuộc vào ngân sách bộ nhớ của bạn.

Vị trí trong series và bước tiếp theo

Series linked list đã đề cập đến: reversal (206), phát hiện cycle (141), merge sorted lists (21), và reorder list (143). Những bài đó thao tác trên một cấu trúc con trỏ đơn. LeetCode 138 là bài đầu tiên trong series buộc bạn phải copy một cấu trúc — và đặc biệt, copy một cấu trúc có reference graph không phải chuỗi đơn giản.

Insight có thể chuyển giao: khi bạn cần deep copy một cấu trúc có cross-reference phức tạp, hãy build tất cả node trước, sau đó nối con trỏ.

Clone Graph (LeetCode 133) là tổng quát hóa trực tiếp. Thay vì linked list với một random pointer mỗi node, bạn có undirected graph với mỗi node có tùy ý nhiều neighbor. Hash map approach từ Approach 1 ở trên áp dụng gần như nguyên văn — build map từ gốc sang clone, sau đó điền các neighbor list. Kỹ thuật interweaving không chuyển giao gọn gàng sang đồ thị tổng quát, nên hash map thắng ở đó.

Clone Binary Tree With Random Pointer (LeetCode 1485) áp dụng cùng random pointer extension cho binary tree. Bạn có left, right, và random. Cấu trúc hai giai đoạn từ Approach 1 — pre-build tất cả clone, sau đó nối — áp dụng trực tiếp. Duyệt là tree DFS thay vì linear scan.

Flatten a Multilevel Doubly Linked List (LeetCode 430) là hương vị khác: danh sách có child pointer tạo ra cấu trúc multi-level, và bạn cần flatten xuống thành single-level doubly linked list. Không có deep copy, nhưng độ phức tạp thao tác con trỏ tương đương — bạn đang nối lại một cấu trúc có cross-link không tuần tự.

LRU Cache (LeetCode 146) liền kề về mặt cấu trúc: nó kết hợp hash map với doubly linked list và yêu cầu nối con trỏ cẩn thận trong mỗi lần insert và delete. Kỷ luật theo dõi con trỏ nào tồn tại và chúng nên trỏ đến đâu — kỹ năng cốt lõi trong LeetCode 138 — là kỹ năng tương tự mà LRU Cache đòi hỏi.