Skip to content

008 — Intersection of Two Linked Lists

Source

  • 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-এর দূরত্ব মেলানো)

1. Problem in simple words

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

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

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

2. Which basic idea does this inherit from?

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

3. What is the hidden math or logic?

লুকানো অঙ্ক চমৎকার। ধরো 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-এ পৌঁছে থামে।

4. Which data structure is needed?

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

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

5. Why this data structure fits

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

6. Real-life analogy

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

7. Visual explanation

a listA থেকে, b listB থেকে; শেষ ছুঁলে অন্যটার head-এ লাফ:

listA: 4 -> 1 -> 8 -> 4 -> 5        (a = 5)
listB: 5 -> 6 -> 1 -> 8 -> 4 -> 5   (b = 6), শেয়ার: 8 -> 4 -> 5

a-এর পথ: 4 1 8 4 5 [None→B] 5 6 1 8 ...
b-এর পথ: 5 6 1 8 4 5 [None→A] 4 1 8 ...
                                  ↑
দুজনেই 5+6-3 = 8 step পর একই node (8)-এ মেলে → return (8)

না মিললে দুজন একসাথে None-এ পৌঁছে থামে → return None

8. Example input and 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

9. Brute force thinking

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

A-এর প্রতি node x:
    B-এর প্রতি node y:
        if x is y: return x
return None

10. Why brute force is slow

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

11. Key observation

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

12. Optimized intuition

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

13. Thinking tweak

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

14. Step-by-step dry run

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-এ এসে মেলে।

15. Python solution

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

16. Line-by-line code explanation

  • 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 (মিল নেই)।

17. Output walkthrough

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

18. Time complexity

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

19. Space complexity

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

20. Common mistakes

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

21. Which basic problem this inherits from

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

22. Similar harder problems

23. Pattern learned

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

24. Final summary

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

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