018 — Copy List with Random Pointer¶

Source¶

Original source: Classic linked list exercise
Platform: LeetCode — https://leetcode.com/problems/copy-list-with-random-pointer/
Topic: linked list
Difficulty: Medium
Pattern: hash map (old → new) / interleaving
Basic idea inherited from: rewiring discipline + map-as-memory (পুরোনোকে নতুনের সাথে map করে রাখা)

1. Problem in simple words¶

একটা linked list দেওয়া, যার প্রতিটা node-এ স্বাভাবিক next arrow ছাড়াও একটা random arrow আছে — যেটা list-এর যেকোনো node-এ (বা None-এ) তাক করতে পারে। তোমাকে পুরো list-এর একটা deep copy বানাতে হবে: নতুন node গুলো হবে আলাদা object, কিন্তু তাদের next ও random গঠন হুবহু আসলটার মতো।

node-এ দুটো arrow:  .next   → পরের node
                     .random → যেকোনো node বা None
copy-তে: সব নতুন object, কিন্তু একই pattern-এ জোড়া

2. Which basic idea does this inherit from?¶

ভিত্তি হলো map-as-memory: পুরোনো node-কে চাবি ধরে তার নতুন copy-কে value-তে রাখা (old → new)। সাথে আগের সব problem-এর rewiring discipline — arrow সাবধানে জোড়া। নতুনত্ব শুধু একটাই: এখানে দুই রকম arrow (next আর random) দুটোই ঠিকঠাক copy করতে হয়।

3. What is the hidden math or logic?¶

লুকানো logic: copy করার সময় random arrow সমস্যা বানায় কারণ যে node-এ random তাক করছে, সেটা এখনো হয়তো তৈরিই হয়নি। সমাধানের চাবি — প্রতিটা পুরোনো node-এর সাথে তার নতুন copy-র একটা mapping (hash map) রাখা। একবার সব copy বানিয়ে map-এ তুলে রাখলে, যেকোনো arrow (next হোক বা random) আসলে "পুরোনো target → তার copy" — এক lookup-এই পাওয়া যায়।

4. Which data structure is needed?¶

একটা hash map (dictionary): চাবি = পুরোনো node, value = তার নতুন copy। এটাই "কোন পুরোনো node-এর copy কোনটা" — সেই স্মৃতি ধরে রাখে।

5. Why this data structure fits¶

random arrow যেকোনো জায়গায় তাক করতে পারে, তাই copy করার সময় target-এর copy আমাদের তাৎক্ষণিক দরকার — খুঁজতে গেলে প্রতিবার পুরো list হাঁটতে হতো (O(n) প্রতি node → O(n²))। hash map সেই lookup-কে O(1) করে দেয়: পুরোনো node হাতে থাকলেই তার copy এক ধাক্কায় পাওয়া যায়। তাই map-ই এখানে নিখুঁত।

6. Real-life analogy¶

একটা বন্ধুর তালিকা copy করছ, যেখানে প্রতিজনের পাশে "এর best friend কে" লেখা আছে (random arrow)। আগে সবার জন্য নতুন খালি কার্ড বানাও আর একটা টেবিলে লিখে রাখো "পুরোনো রাহুল → নতুন রাহুল"। তারপর প্রতিটা নতুন কার্ডে best-friend লিখতে গিয়ে টেবিল দেখে নাও — "পুরোনো best friend-এর নতুন কার্ড কোনটা"। টেবিলটাই hash map।

7. Visual explanation¶

দুই pass; map = {পুরোনো: নতুন}:

পুরোনো:  A → B → C        A.random=C,  B.random=A,  C.random=None

pass 1 (copy বানাও, map-এ রাখো):
  map = { A:A', B:B', C:C' }     (A', B', C' নতুন object)

pass 2 (next ও random জোড়ো, map দেখে):
  A'.next = map[B] = B'          A'.random = map[C] = C'
  B'.next = map[C] = C'          B'.random = map[A] = A'
  C'.next = map[None] = None     C'.random = map[None] = None

ফল: A' → B' → C'  (সব নতুন object, একই random গঠন)

8. Example input and output¶

(প্রতিটা node [val, random_index]; index = কোন node-এ random তাক করছে, None = কোথাও না)

Input : [[7,None],[13,0],[11,4],[10,2],[1,0]]
Output: একই গঠনের সম্পূর্ণ নতুন list (সব node নতুন object)

Edge 1 (খালি): None        -> Output: None
Edge 2 (একটা node, নিজের দিকে random): [[1,0]] -> Output: [[1,0]] (নতুন object)

9. Brute force thinking¶

সরল চিন্তা (map ছাড়া): প্রথমে শুধু next ধরে নতুন list বানাও। তারপর random জোড়াতে — প্রতিটা পুরোনো node-এর random কততম node-এ তাক করছে সেটা পুরোনো list হেঁটে গুনে বের করো, তারপর নতুন list-এ ততবার হেঁটে সেই copy খুঁজে random সেট করো।

প্রতিটা node-এর random-এর জন্য:
  পুরোনো list হেঁটে index বের করো
  নতুন list হেঁটে সেই index-এ পৌঁছে random সেট করো

10. Why brute force is slow¶

প্রতিটা node-এর random ঠিক করতে দুবার list হাঁটতে হয় (index বের করা + নতুন list-এ পৌঁছানো) — প্রতি node-এ O(n), মোট O(n²)। hash map ব্যবহার করলে এই বারবার খোঁজা মুছে যায়: পুরোনো node → copy সরাসরি O(1)-তে, তাই পুরোটা O(n)-এ নামে।

11. Key observation¶

মূল observation: প্রতিটা arrow (next হোক বা random) আসলে একটা পুরোনো node-এ তাক করে; আমার শুধু "সেই পুরোনো node-এর copy কে" জানা দরকার। যদি আগে সব copy বানিয়ে old → new map-এ তুলে রাখি, তাহলে যেকোনো arrow এক lookup-এই জোড়া যায়।

12. Optimized intuition¶

দুই pass: pass 1-এ list হেঁটে প্রতিটা পুরোনো node-এর জন্য একটা নতুন node বানাও, map-এ old → new রাখো (এখনো arrow জুড়ো না)। pass 2-এ আবার হেঁটে প্রতিটা copy-র next = map[old.next] আর random = map[old.random] সেট করো। map.get(None) স্বাভাবিকভাবেই None ফেরায়, তাই None target আলাদা করে সামলাতে হয় না।

13. Thinking tweak¶

মোচড়: "random তো এমন node-এ তাক করছে যেটা এখনো বানাইনি" — এই আতঙ্ক বাদ দাও। আগে সব copy বানিয়ে map-এ তুলে নাও; তখন আর কোনো target "অস্তিত্বহীন" থাকে না, যেকোনো arrow এক lookup-এ বসে যায়। বানানো আর জোড়া — দুই কাজ দুই pass-এ আলাদা করো।

14. Step-by-step dry run¶

Input A → B, A.random = B, B.random = B:

pass 1: A-এর copy A' বানাও, map = {A:A'}; B-এর copy B', map = {A:A', B:B'}।
pass 2 (A): A'.next = map[B] = B'; A'.random = map[B] = B'।
pass 2 (B): B'.next = map[None] = None; B'.random = map[B] = B'।
ফল: A' → B', যেখানে A'.random = B', B'.random = B' — গঠন হুবহু এক, সব নতুন object।

15. Python solution¶

class Node:
    def __init__(self, val=0, next=None, random=None):
        self.val = val
        self.next = next
        self.random = random

def copy_random_list(head):
    if not head:
        return None

    old_to_new = {}                 # পুরোনো node → তার নতুন copy

    # pass 1: প্রতিটা node-এর copy বানাও, map-এ রাখো (arrow এখনো নয়)
    cur = head
    while cur:
        old_to_new[cur] = Node(cur.val)
        cur = cur.next

    # pass 2: copy গুলোর next ও random map দেখে জোড়ো
    cur = head
    while cur:
        old_to_new[cur].next = old_to_new.get(cur.next)      # None হলে None
        old_to_new[cur].random = old_to_new.get(cur.random)  # None হলে None
        cur = cur.next

    return old_to_new[head]

# ---- helpers (test-এর জন্য) ----
def build_with_random(pairs):
    # pairs: [(val, random_index বা None), ...]
    nodes = [Node(v) for v, _ in pairs]
    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]
    for i, (_, r) in enumerate(pairs):
        nodes[i].random = nodes[r] if r is not None else None
    return nodes[0] if nodes else None

def to_pairs(head):
    nodes = []
    cur = head
    while cur:
        nodes.append(cur)
        cur = cur.next
    idx = {node: i for i, node in enumerate(nodes)}
    return [(n.val, idx[n.random] if n.random is not None else None) for n in nodes]

def node_list(head):
    out = []
    while head:
        out.append(head)
        head = head.next
    return out

# ---- tests ----
original = build_with_random([(7, None), (13, 0), (11, 4), (10, 2), (1, 0)])
copied = copy_random_list(original)

# গঠন (value + random index) হুবহু মেলে
assert to_pairs(original) == [(7, None), (13, 0), (11, 4), (10, 2), (1, 0)]
assert to_pairs(copied) == to_pairs(original)

# প্রতিটা copy অবশ্যই নতুন object (deep copy)
o_nodes, c_nodes = node_list(original), node_list(copied)
assert len(o_nodes) == len(c_nodes)
assert all(o is not c for o, c in zip(o_nodes, c_nodes))

# edge: খালি ও একক node (নিজের দিকে random)
assert copy_random_list(None) is None
single = build_with_random([(1, 0)])
csingle = copy_random_list(single)
assert to_pairs(csingle) == [(1, 0)] and csingle is not single
print("সব test pass!")

16. Line-by-line code explanation¶

if not head: return None — খালি list-এর copy খালি।
old_to_new = {} — মূল স্মৃতি: পুরোনো node-কে চাবি ধরে তার copy।
pass 1 loop — শুধু Node(cur.val) বানিয়ে map-এ রাখো; arrow এখনো জোড়ো না (target হয়তো অনাগত)।
pass 2 loop — old_to_new.get(cur.next) ও old_to_new.get(cur.random) দিয়ে copy-র দুই arrow সেট; .get() ব্যবহারে None target এমনিতেই None হয়।
return old_to_new[head] — পুরোনো head-এর copy-ই নতুন list-এর head।

17. Output walkthrough¶

LeetCode-এর classic example [[7,None],[13,0],[11,4],[10,2],[1,0]] দিয়ে: pass 1-এ ৫টা নতুন node map-এ ওঠে; pass 2-এ প্রতিটার next/random map দেখে বসে। to_pairs(copied) দেয় হুবহু [(7,None),(13,0),(11,4),(10,2),(1,0)] — original-এর সমান, কিন্তু সব node নতুন object (o is not c)। খালি ও একক-node case-ও pass; শেষে print: সব test pass!।

18. Time complexity¶

O(n) — দুটো আলাদা pass, প্রতিটায় n node একবার করে; map lookup O(1)।

19. Space complexity¶

O(n) — map-এ n-টা old → new entry। (interleaving / weaving কৌশলে map বাদ দিয়ে O(1) extra-তে নামানো যায়, কিন্তু code জটিল হয়।)

20. Common mistakes¶

এক pass-এ next/random জোড়ার চেষ্টা — random এমন node-এ তাক করতে পারে যার copy এখনো বানানো হয়নি → KeyError বা ভুল।
None target আলাদা করে না সামলানো — map[None] KeyError দিত; তাই map.get(...) ব্যবহার করো।
shallow copy বানানো (পুরোনো node গুলোই ফেরত দেওয়া) — তখন copy আলাদা object নয়; "deep copy" শর্ত ভাঙে।
খালি list (head = None) আলাদা না ভাবা — old_to_new[head]-এ KeyError।

21. Which basic problem this inherits from¶

ভিত্তি: hash map-কে "স্মৃতি" হিসেবে ব্যবহার করা (পুরোনো → নতুন mapping) আর আগের সব problem-এর rewiring discipline। Map-as-memory idea-টা hash map chapter-এর সাথেও জোড়া।

22. Similar harder problems¶

Clone Graph (একই map-as-memory, graph-এ) — https://leetcode.com/problems/clone-graph/
Copy List with Random Pointer-এর O(1)-space interleaving রূপ (একই link, weaving approach) — https://leetcode.com/problems/copy-list-with-random-pointer/
Linked List Components — https://leetcode.com/problems/linked-list-components/

23. Pattern learned¶

Map-as-memory (old → new): copy/clone problem-এ পুরোনো object-কে নতুন object-এর সাথে map করে রাখা, তারপর arrow/edge গুলো এক lookup-এ জোড়া।

24. Final summary¶

ভবিষ্যতের আমাকে: "random/এলোমেলো pointer-ওয়ালা কিছু copy করতে হবে? আগে সব node copy করে old → new map বানাও, তারপর দ্বিতীয় pass-এ map দেখে সব arrow জোড়ো।" 'target এখনো বানাইনি'-র সমাধান = আগে সব বানাও, পরে জোড়ো।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।