কনটেন্টে যান

018 — Copy List with Random Pointer

Problem link ও উৎস

  • 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 করে রাখা)

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

একটা 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-এ জোড়া

Input ও 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)

চেনা উদাহরণে বোঝা

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

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

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

ভেতরের যুক্তি

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

কী দিয়ে তথ্য রাখব

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

এটি কেন উপযুক্ত

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

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

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

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

কোথায় বেশি কাজ হচ্ছে

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

যে বিষয়টি খেয়াল করতে হবে

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

আরও কম কাজে সমাধান

দুই 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 আলাদা করে সামলাতে হয় না।

ভাবনার পরিবর্তন

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

ছবিতে বোঝা

দুই 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 গঠন)

ছোট input-এ ধাপে ধাপে

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।

কোড ও ব্যাখ্যা

Python

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!")

কোডের প্রতিটি অংশ

  • 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 মিলিয়ে দেখা

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!।

খরচ ও সাধারণ ভুল

সময়

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

অতিরিক্ত জায়গা

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

যে ভুলগুলো এড়াতে হবে

  • এক 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।

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

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

পরের অনুশীলন

কৌশলটি মনে রাখুন

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

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে: "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।