কনটেন্টে যান

008 — Intersection of Two Linked Lists

Problem link ও উৎস

  • Original source: Classic linked list exercise
  • Platform: LeetCode — https://leetcode.com/problems/intersection-of-two-linked-lists/
  • Topic: linked list
  • Difficulty: Easy
  • Pattern: two pointers / path switching
  • Basic idea inherited from: runner / gap thinking (দুই pointer-এর দূরত্ব মেলানো)

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

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

দুটো singly linked list দেওয়া। এরা হতে পারে কোনো এক জায়গায় গিয়ে মিলে যায় — মানে সেখান থেকে শেষ পর্যন্ত দুটোরই একই node গুলো শেয়ার করা (একই object, শুধু সমান value নয়)। প্রথম যেখানে এরা মেলে, সেই intersection node-টা return করো। না মিললে None।

উদাহরণ
listA:      4 -> 1
                   \
                    8 -> 4 -> 5      (এই লেজটা শেয়ার করা)
                   /
listB: 5 -> 6 -> 1

মিলনস্থল = node (8)

Input ও output

উদাহরণ
listA: 4 -> 1 -> 8 -> 4 -> 5
listB: 5 -> 6 -> 1 -> 8 -> 4 -> 5    (8 থেকে শেয়ার)
Output: node (8)        (একই object, value নয়)

Edge (মিল নেই): listA: 2 -> 6 -> 4 , listB: 1 -> 5   -> Output: None

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

দুই বন্ধু আলাদা দুই গলি দিয়ে হেঁটে একই মূল রাস্তায় ওঠে, তারপর একসাথে গন্তব্যে যায়। গলি দুটোর দৈর্ঘ্য আলাদা বলে কে আগে মূল রাস্তায় উঠবে তা ভিন্ন। চালাকি: যে আগে নিজের পথ শেষ করবে, সে অন্যজনের শুরুর বিন্দু থেকে আবার হাঁটা ধরবে। এতে দুজনের মোট হাঁটা সমান হয়ে যায়, আর তারা ঠিক মূল রাস্তার মুখে একসাথে এসে দেখা করে।

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

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

ভিত্তি runner / gap thinking — দুই pointer চালানোর সময় তাদের মধ্যে দূরত্ব বা শুরুর অবস্থান কীভাবে মেলানো যায়। slow/fast পরিবারের ([003-linked-list-cycle.md](003-linked-list-cycle.md)) মতোই দুই pointer, কিন্তু এখানে গতি সমান; চালাকিটা হলো পথ অদলবদল করে দুজনকে সমান দূরত্ব হাঁটানো, যাতে তারা ঠিক মিলনস্থলে এসে মেলে।

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

লুকানো অঙ্ক চমৎকার। ধরো A-এর দৈর্ঘ্য a, B-এর b, শেয়ার-করা লেজ c। pointer pa যদি A শেষ করে B-তে লাফায়, সে মোট হাঁটে a + (b - c); pb B শেষ করে A-তে লাফালে হাঁটে b + (a - c)। দুটোই সমান a + b - c! তাই ঠিক একই step-এ দুজন intersection node-এ পৌঁছায়। না মিললে c = 0, দুজনেই a + b step পরে একসাথে None-এ পৌঁছে থামে।

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

দুই রকম সমাধান:

  • সহজ: A-এর সব node একটা hash set-এ রাখো; তারপর B হেঁটে প্রথম যে node set-এ আছে — সেটাই উত্তর। O(n) extra space।
  • সেরা: দুটো pointer, পথ অদলবদল করে — কোনো extra structure ছাড়াই, O(1) space।

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

set লাগলে O(m) memory। কিন্তু দুই pointer-এর কৌশলে আমরা শুধু গতি ও পথ নিয়ে খেলি — দৈর্ঘ্যের পার্থক্যটা "পথ অদলবদল" আপনাআপনি মুছে দেয়, তাই আলাদা করে length গুনতে বা set বানাতে হয় না। এটাই O(1) space-এ intersection ধরার নিখুঁত উপায়। আর তুলনা হয় node identity (is) দিয়ে — value নয়।

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

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

সরল চিন্তা: A-এর প্রতিটা node-এর জন্য, B-এর পুরোটা ঘুরে দেখো একই object (is) পাওয়া যায় কিনা। প্রথম যেটায় মেলে সেটাই উত্তর।

উদাহরণ
A-এর প্রতি node x:
    B-এর প্রতি node y:
        if x is y: return x
return None

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

এই nested loop O(a × b) — বড় list-এ ধীর। hash set দিয়ে O(a + b) সময়ে নামানো যায়, কিন্তু O(a) extra space লাগে। দুই-pointer পথ-অদলবদল কৌশল একই O(a + b) সময়ে কাজটা করে, তবে O(1) space-এ — তাই সেরা।

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

মূল observation: দৈর্ঘ্যের পার্থক্যই আসল বাধা — না হলে দুজনকে একসাথে চালিয়ে দিলেই মিলনস্থলে মিলত। আর পার্থক্য মেটানোর সহজ উপায়: প্রত্যেকে অন্যজনের পথটাও হেঁটে নিক, তাহলে দুজনের মোট দূরত্ব সমান (a + b) হয়ে যায়।

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

দুটো pointer a (headA থেকে) আর b (headB থেকে) ছাড়ো। প্রতি step-এ দুজনেই এক ঘর এগোয়; কেউ None ছুঁলে সে অন্য list-এর head থেকে আবার শুরু করে। এভাবে দুজনের অতিক্রান্ত দূরত্ব সমান হয়, ফলে তারা ঠিক intersection node-এ এসে মেলে (a is b)। মিল না থাকলে দুজনেই একসাথে None হয় — তখন None ফেরত।

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

মোচড়: length গুনে পার্থক্য মেলানোর ঝামেলায় যেও না — শুধু "শেষ হলে অন্যজনের শুরুতে লাফ দাও।" এই এক চালেই দুই পথ সমান দৈর্ঘ্যের হয়ে যায়, আর মিলনস্থল নিজে থেকে ধরা দেয়। গণিতকে গতির কৌশলে লুকিয়ে ফেলা।

ছবিতে বোঝা

একই value মানেই একই node নয়। A0,A1,B0,B1,B2 আলাদা object; C0,C1,C2 দুই list-এ একই object।

graph LR
 A0["A0:4"] --> A1["A1:1"] --> C0["C0:8"] --> C1["C1:4"] --> C2["C2:5"] --> N["None"]
 B0["B0:5"] --> B1["B1:6"] --> B2["B2:1"] --> C0
loop update-এর সংখ্যা pointer a pointer b
0 A0 B0
1 A1 B1
2 C0 B2
3 C1 C0
4 C2 C1
5 None C2
6 B0 None
7 B1 A0
8 B2 A1
9 C0 C0

এখানে None থেকে অন্য head-এ যাওয়াও একটি loop update। তাই 9 update-এর পরে identity মেলে, return C0। Intersection না থাকলে দুজন একই সময়ে None-এ পৌঁছায়।

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

listA = 4 -> 1 -> 8, listB = 5 -> 8, যেখানে 8 দুই list-এর একই (শেয়ার করা) node (a=3, b=2, c=1):

  1. শুরু: a=4, b=5
  2. a=1, b=8
  3. a=8, b=None
  4. a=None (A শেষ), b=4 (B শেষ → A-এর head-এ লাফ)
  5. a=5 (A শেষ → B-এর head-এ লাফ), b=1
  6. a=8 (শেয়ার), b=8 (শেয়ার) → a is b সত্যি → return 8

খেয়াল করো, দুজনের মোট হাঁটা সমান (a + b - c = 4) — তাই তারা ঠিক শেয়ার করা 8-এ এসে মেলে।

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

Python

Python
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def get_intersection_node(headA, headB):
    if not headA or not headB:
        return None
    a, b = headA, headB
    while a is not b:                  # node identity, value নয়
        a = a.next if a else headB     # A শেষ হলে B-এর head-এ লাফ
        b = b.next if b else headA     # B শেষ হলে A-এর head-এ লাফ
    return a                           # শেয়ার করা node, বা দুজনেই None

# ---- helpers (test-এর জন্য) ----
def build(values):
    dummy = ListNode()
    tail = dummy
    for v in values:
        tail.next = ListNode(v)
        tail = tail.next
    return dummy.next

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

def tail_of(head):
    cur = head
    while cur.next:                    # শেষ node পর্যন্ত হাঁটো
        cur = cur.next
    return cur

# ---- tests ----
# মিল আছে: শেয়ার করা লেজ একবার বানিয়ে দুই prefix-এ জুড়ি
shared = build([8, 4, 5])
listA = build([4, 1])
listB = build([5, 6, 1])
tail_of(listA).next = shared          # 4 -> 1 -> [8 -> 4 -> 5]
tail_of(listB).next = shared          # 5 -> 6 -> 1 -> [8 -> 4 -> 5]
assert to_list(listA) == [4, 1, 8, 4, 5]
assert to_list(listB) == [5, 6, 1, 8, 4, 5]
assert get_intersection_node(listA, listB) is shared   # একই object ফেরে

# মিল নেই
c = build([2, 6, 4])
d = build([1, 5])
assert get_intersection_node(c, d) is None
print("সব test pass!")

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

  • if not headA or not headB: return None — কোনো একটা list খালি হলে মিল অসম্ভব।
  • a, b = headA, headB — দুজন নিজ নিজ head থেকে শুরু।
  • while a is not b: — is মানে একই object; সমান value আলাদা node-কে ভুল করে মেলায় না।
  • a = a.next if a else headB — a শেষ (None) হলে B-এর head-এ লাফ, নাহলে এক ঘর।
  • b = b.next if b else headA — b-এর জন্য একই, উল্টো list-এ।
  • return a — loop থামে যখন a is b: হয় শেয়ার করা node, নয়তো দুজনেই None (মিল নেই)।

Output মিলিয়ে দেখা

shared = [8,4,5] একবার বানিয়ে listA = 4->1->shared ও listB = 5->6->1->shared জোড়া হলো — তাই 8-node দুই list-এ একই object। দুই pointer পথ অদলবদল করে ঠিক 8-এ মেলে, is shared সত্যি। মিল-না-থাকা c, d-তে দুজন একসাথে None-এ থামে → None। সব assert pass → সব test pass!।

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

সময়

O(a + b) — প্রতিটা pointer বড়জোর a + b ঘর হাঁটে (নিজের list + অন্যটা), তারপরেই মেলে বা None।

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

O(1) — শুধু দুটো pointer; hash set-এর O(a) লাগে না।

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

  • a == b (value তুলনা) লেখা a is b-এর বদলে — দুই আলাদা node-এর value সমান হলে ভুল উত্তর।
  • "মিল নেই" ক্ষেত্রে loop কেন থামে বুঝতে ভুল করা — দুজনেই একসাথে None হয়, তাই a is b (None is None) সত্যি হয়ে থামে; None চেক আলাদা করে না করলেও চলে।
  • length আগে গুনে পার্থক্য সরিয়ে দেওয়ার দীর্ঘ পথে যাওয়া — কাজ করে, কিন্তু path-switching অনেক পরিষ্কার।

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

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

ভিত্তি: runner/gap thinking — দুই pointer-এর দূরত্ব/অবস্থান মেলানো (../patterns.md-এর runner অংশ; slow/fast পরিবার [003-linked-list-cycle.md](003-linked-list-cycle.md))। node identity ও traversal-এর ছবি ../operations.md-তে।

পরের অনুশীলন

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

Two pointers with path switching: দুই pointer অন্যজনের পথও হেঁটে নিলে তাদের মোট দূরত্ব সমান হয়; ফলে তারা ঠিক মিলনস্থলে (বা একসাথে None-এ) মেলে — length না গুনে, O(1) space-এ।

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

ভবিষ্যতের আমাকে: "দুই list কোথায় মেলে? length গুনো না — দুই pointer ছাড়ো, শেষ হলে অন্যজনের head-এ লাফ দাও; তারা মিলনস্থলে মিলবে বা একসাথে None হবে।" তুলনা সবসময় is দিয়ে। দৈর্ঘ্যের পার্থক্য মেটানোর সবচেয়ে মার্জিত কৌশল।

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