Problem link ও উৎস
- **Original source:** Classic linked list exercise
- **Platform:** LeetCode —
- **Topic:** linked list
- **Difficulty:** Easy
- **Pattern:** two pointers / path switching
- **Basic idea inherited from:** runner / gap thinking (দুই pointer-এর দূরত্ব মেলানো)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
দুটো singly linked list দেওয়া। এরা হতে পারে কোনো এক জায়গায় গিয়ে **মিলে যায়** — মানে সেখান থেকে শেষ পর্যন্ত দুটোরই একই node গুলো শেয়ার করা (একই object, শুধু সমান value নয়)। প্রথম যেখানে এরা মেলে, সেই **intersection node**-টা return করো। না মিললে `None`।
```text
listA: 4 -> 1
\
8 -> 4 -> 5 (এই লেজটা শেয়ার করা)
/
listB: 5 -> 6 -> 1
মিলনস্থল = node (8)
```
### Input ও output {#8-example-input-and-output}
```text
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
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
দুই বন্ধু আলাদা দুই গলি দিয়ে হেঁটে একই মূল রাস্তায় ওঠে, তারপর একসাথে গন্তব্যে যায়। গলি দুটোর দৈর্ঘ্য আলাদা বলে কে আগে মূল রাস্তায় উঠবে তা ভিন্ন। চালাকি: যে আগে নিজের পথ শেষ করবে, সে অন্যজনের শুরুর বিন্দু থেকে আবার হাঁটা ধরবে। এতে দুজনের মোট হাঁটা সমান হয়ে যায়, আর তারা ঠিক **মূল রাস্তার মুখে** একসাথে এসে দেখা করে।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত্তি **runner / gap thinking** — দুই pointer চালানোর সময় তাদের মধ্যে দূরত্ব বা শুরুর অবস্থান কীভাবে মেলানো যায়। slow/fast পরিবারের ([[003-linked-list-cycle.md](003-linked-list-cycle.md)](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 নয়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
সরল চিন্তা: A-এর **প্রতিটা** node-এর জন্য, B-এর পুরোটা ঘুরে দেখো একই object (`is`) পাওয়া যায় কিনা। প্রথম যেটায় মেলে সেটাই উত্তর।
```text
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 গুনে পার্থক্য মেলানোর ঝামেলায় যেও না — শুধু "শেষ হলে অন্যজনের শুরুতে লাফ দাও।" এই এক চালেই দুই পথ সমান দৈর্ঘ্যের হয়ে যায়, আর মিলনস্থল নিজে থেকে ধরা দেয়। গণিতকে গতির কৌশলে লুকিয়ে ফেলা।
### ছবিতে বোঝা {#7-visual-explanation}
একই value মানেই একই node নয়। A0,A1,B0,B1,B2 আলাদা object; C0,C1,C2 দুই list-এ একই object।
```mermaid
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-এ ধাপে ধাপে {#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`-এ এসে মেলে।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```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!")
```
### কোডের প্রতিটি অংশ {#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` (মিল নেই)।
### Output মিলিয়ে দেখা {#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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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 অনেক পরিষ্কার।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: runner/gap thinking — দুই pointer-এর দূরত্ব/অবস্থান মেলানো ([../patterns.md](../patterns.md)-এর runner অংশ; slow/fast পরিবার [[003-linked-list-cycle.md](003-linked-list-cycle.md)](003-linked-list-cycle.md))। node identity ও traversal-এর ছবি [../operations.md](../operations.md)-তে।
### পরের অনুশীলন {#22-similar-harder-problems}
- Linked List Cycle II (দূরত্ব-বীজগণিত দিয়ে মিলনস্থল) —