Problem link ও উৎস
- **Original source:** Classic linked list exercise
- **Platform:** LeetCode —
- **Topic:** linked list
- **Difficulty:** Medium
- **Pattern:** hash map (old → new) / interleaving
- **Basic idea inherited from:** rewiring discipline + map-as-memory (পুরোনোকে নতুনের সাথে map করে রাখা)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা linked list দেওয়া, যার প্রতিটা node-এ স্বাভাবিক `next` arrow ছাড়াও একটা **`random`** arrow আছে — যেটা list-এর যেকোনো node-এ (বা `None`-এ) তাক করতে পারে। তোমাকে পুরো list-এর একটা **deep copy** বানাতে হবে: নতুন node গুলো হবে আলাদা object, কিন্তু তাদের `next` ও `random` গঠন হুবহু আসলটার মতো।
```text
node-এ দুটো arrow: .next → পরের node
.random → যেকোনো node বা None
copy-তে: সব নতুন object, কিন্তু একই pattern-এ জোড়া
```
### Input ও output {#8-example-input-and-output}
(প্রতিটা node `[val, random_index]`; index = কোন node-এ random তাক করছে, `None` = কোথাও না)
```text
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)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
একটা বন্ধুর তালিকা copy করছ, যেখানে প্রতিজনের পাশে "এর best friend কে" লেখা আছে (random arrow)। আগে সবার জন্য নতুন খালি কার্ড বানাও আর একটা টেবিলে লিখে রাখো "পুরোনো রাহুল → নতুন রাহুল"। তারপর প্রতিটা নতুন কার্ডে best-friend লিখতে গিয়ে টেবিল দেখে নাও — "পুরোনো best friend-এর নতুন কার্ড কোনটা"। টেবিলটাই hash map।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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-ই এখানে নিখুঁত।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
সরল চিন্তা (map ছাড়া): প্রথমে শুধু `next` ধরে নতুন list বানাও। তারপর random জোড়াতে — প্রতিটা পুরোনো node-এর random কততম node-এ তাক করছে সেটা পুরোনো list হেঁটে গুনে বের করো, তারপর নতুন list-এ ততবার হেঁটে সেই copy খুঁজে random সেট করো।
```text
প্রতিটা 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-এ আলাদা করো।
### ছবিতে বোঝা {#7-visual-explanation}
দুই pass; map = `{পুরোনো: নতুন}`:
```text
পুরোনো: 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 গঠন)
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `A → B`, `A.random = B`, `B.random = B`:
1. pass 1: A-এর copy A' বানাও, `map = {A:A'}`; B-এর copy B', `map = {A:A', B:B'}`।
2. pass 2 (A): `A'.next = map[B] = B'`; `A'.random = map[B] = B'`।
3. pass 2 (B): `B'.next = map[None] = None`; `B'.random = map[B] = B'`।
4. ফল: `A' → B'`, যেখানে `A'.random = B'`, `B'.random = B'` — গঠন হুবহু এক, সব নতুন object।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
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।
### Output মিলিয়ে দেখা {#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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#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-এ) —