Linked List — Problem-Solving Patterns¶

পাঁচটা named pattern-ই linked-list interview question-এর বিশাল বড় অংশটা cover করে। প্রতিটা entry-তে: trigger word, core idea, thinking tweak, ছোট্ট একটা worked example, কী থেকে inherit করে, আর কোথায় practice করবে।

Pattern 1 — Slow/Fast Pointers (tortoise and hare)¶

Trigger words: "middle of the list", "is there a cycle", "where does the cycle start", "happy number" (হ্যাঁ — function iteration আসলে একটা লুকানো linked list)।

Core idea: দুটো pointer একসাথে traverse করে, কিন্তু আলাদা speed-এ (1 hop vs 2 hop)। তাদের relative motion-ই তথ্য encode করে: দেখা হওয়া প্রমাণ করে cycle আছে; fast শেষ করা মানে slow midpoint-এ দাঁড়িয়ে।

The thinking tweak: "প্রতিটা pointer কোথায়" ভাবা বন্ধ করে ভাবা শুরু করো "তাদের মাঝের gap-টা কী করছে"। Cycle-এর ভেতরে gap প্রতি step-এ ঠিক 1 করে কমে — তাই দেখা হওয়াটা অনিবার্য, ভাগ্যের ব্যাপার না।

Worked example — 1→2→3→4→5→(back to 3)-এ cycle check:

step 0: slow=1 fast=1
step 1: slow=2 fast=3
step 2: slow=3 fast=5
step 3: slow=4 fast=4   <- same NODE (identity). Cycle exists.
no cycle case: fast hits None first, answer is False.

Bonus (cycle-এর entry point): দেখা হওয়ার পরে, একটা pointer-কে head-এ reset করো, দুজনকেই এক hop করে সরাও — তারা ঠিক cycle-এর শুরুতে গিয়ে মেলে। এটাই Floyd's full algorithm; distance-এর algebra-টা সাজানো আছে Wikipedia: Cycle detection-এ।

Inherits from: সাধারণ traversal — এটা আসলে দুটো traversal loop এক pass-এ গলিয়ে দেওয়া।

Representative problems:

Cycle detect করো — LeetCode 141
Cycle-এর entry node খোঁজো — LeetCode 142
এক pass-এ middle — LeetCode 876

Pattern 2 — Dummy Head Node¶

Trigger words: যে problem-এ head নিজেই হয়তো তার আগে insert হবে, delete হবে, বা replace হবে: "remove all nodes with value X", "merge", "partition", "delete duplicates"।

Core idea: একটা ফেলনা node dummy সামনে বসাও, যার next হলো আসল head। এখন প্রতিটা real node-এর — পুরনো head সহ — একটা predecessor আছে, তাই একটা uniform code path-ই সব position সামলায়। শেষে dummy.next return করো।

The thinking tweak: edge case সাধারণত একটা missing uniform structure-এর লক্ষণ। if deleting_head: ... else: ... লেখার বদলে, দুনিয়াটাই বদলে দাও যাতে head আর special না থাকে।

Worked example — 7 → 7 → 3 → / থেকে সব 7 delete করো:

dummy -> [7] -> [7] -> [3] -> /
prev=dummy: prev.next is 7 -> bypass:   dummy -> [7] -> [3] -> /
prev=dummy: prev.next is 7 -> bypass:   dummy -> [3] -> /
prev=dummy: prev.next is 3 -> keep, advance. prev.next None -> stop.
return dummy.next  ->  [3] -> /        (no special head-handling anywhere)

Inherits from: delete-after-a-node operation; dummy শুধু guarantee দেয় যে একটা "after" সবসময় থাকবে।

Representative problems:

একটা value-র সমান সব element সরাও — LeetCode 203
দুটো sorted list merge করো — LeetCode 21
শেষ থেকে nth সরাও (dummy + runner) — LeetCode 19

Pattern 3 — In-Place Reversal¶

Trigger words: "reverse the list", "reverse between positions", "reverse in groups of k", "reorder", "palindrome check in O(1) space"।

Core idea: তিন-pointer-এর নাচ (prev, cur, nxt): বাকিটা save করো, current arrow flip করো, দুটো frontier pointer-ই advance করো। প্রতিটা node-এর arrow ঠিক একবার flip হয় → O(n) time, O(1) space।

The thinking tweak: list-টাকে দুটো zone হিসেবে ভাবো — একটা বাড়তে থাকা reversed zone (prev যার মাথায়) আর একটা ছোট হতে থাকা untouched zone (cur যার মাথায়)। প্রতিটা loop iteration একটা node-কে সীমানা পার করায়। Save-before-flip ordering-টাই গোটা safety argument।

Worked example — 1 → 2 → 3 reverse করো:

prev=/      cur=1:  save nxt=2; 1->/      ; prev=1, cur=2
prev=1      cur=2:  save nxt=3; 2->1      ; prev=2, cur=3
prev=2      cur=3:  save nxt=/; 3->2      ; prev=3, cur=/
loop ends. head = prev = 3.   Result: 3 -> 2 -> 1 -> /

(Frame-by-frame ছবি: visual-explanation.md section 4।)

Inherits from: দুই লাইনের insert-at-head — reversal আসলে "পুরনো list-এর সামনে থেকে এক এক করে node pop করো আর নতুনটার সামনে push করো"।

Representative problems:

পুরো list reverse করো — LeetCode 206
দুটো position-এর মাঝের sublist reverse করো — LeetCode 92
k-group-এ reverse করো (hard) — LeetCode 25

Pattern 4 — Merge Two Lists¶

Trigger words: "merge two sorted lists", "merge k lists", "sort a linked list" (merge sort-এর combine step), "add two numbers" (carry সহ digit stream-এর একটা merge)।

Core idea: একটা বাড়তে থাকা result-এ (একটা dummy থেকে শুরু) একটা tail pointer রাখো। বারবার দুটো input list-এর সামনের গুলো compare করো, ছোটটাকে tail-এর সাথে link করো, আর সেই input advance করো। একটা list খালি হয়ে গেলে, অন্যটার পুরো বাকি অংশ link করে দাও — কোনো copy ছাড়া।

The thinking tweak: তুমি node বানাচ্ছ না, existing node-দের re-thread করছ। Result list-টা input-দের নিজেদের node দিয়েই বোনা — এজন্যই এটার খরচ O(1) extra space।

Worked example — 1→3→9 আর 2→4 merge করো:

dummy ->                    pick min(1,2)=1:  dummy->1        inputs: 3→9 | 2→4
dummy->1                    pick min(3,2)=2:  dummy->1->2     inputs: 3→9 | 4
dummy->1->2                 pick min(3,4)=3:  dummy->1->2->3  inputs: 9   | 4
dummy->1->2->3              pick min(9,4)=4:  ...->4          inputs: 9   | empty
second list empty -> attach remainder:        dummy->1->2->3->4->9->/

Inherits from: sorted array-র two-pointer merge (../02-arrays-and-strings/, two-pointers pattern) প্লাস উপরের dummy-head pattern।

Representative problems:

দুটো sorted list merge করো — LeetCode 21
k-টা sorted list merge করো — LeetCode 23
একটা linked list O(n log n)-এ sort করো — LeetCode 148

Pattern 5 — Runner Technique (fixed-gap two pointers)¶

Trigger words: "nth node from the end", "in one pass", "delete the kth from the back", "intersection of two lists" (একটা length-offset জাতভাই)।

Core idea: front pointer-কে ঠিক যে gap-টা তোমার দরকার সেই পরিমাণ head start দাও, তারপর front আর back-কে একসাথে সরাও। front শেষ থেকে পড়ে গেলে, back দাঁড়িয়ে থাকে ঠিক gap-from-the-end-এ। এক pass, length আগে গোনার দরকার নেই।

The thinking tweak: শেষে না পৌঁছানো পর্যন্ত তুমি শেষটা দেখতে পাও না — কিন্তু তুমি সাথে করে একটা ruler নিয়ে যেতে পারো। দুই pointer-এর মাঝের fixed gap-টাই হলো সেই ruler।

Worked example — 1→2→3→4→5-এর শেষ থেকে 2nd-টা delete করো:

gap wanted: n+1 = 3 (so back lands on the PREDECESSOR of the target)
dummy->1->2->3->4->5->/
advance front 3 hops from dummy:  back=dummy, front=3
move both:  back=1,front=4   back=2,front=5   back=3,front=/  stop
back=3, so bypass back.next:   1->2->3->5->/        (4 removed)

Inherits from: slow/fast pointers — সেই একই "দুজন একসাথে চলা যাত্রী"-র idea, কিন্তু speed ratio-র জায়গায় একটা constant gap। সাথে dummy-head pattern যোগ করো যাতে আসল head delete করতেও কোনো special case না লাগে।

Representative problems:

শেষ থেকে nth node সরাও — LeetCode 19
দুটো list-এর intersection point — LeetCode 160
List-কে ডানে k ঘুরাও — LeetCode 61

Pattern combine করা (hard problem গুলো যেখানে থাকে)¶

আসল interview problem এই pattern গুলো chain করে:

Problem	Recipe
Palindrome list, O(1) space — LeetCode 234	middle (P1) → দ্বিতীয় অর্ধেক reverse (P3) → two-pointer compare
Reorder list — LeetCode 143	middle (P1) → reverse (P3) → পালা করে merge (P4)
Sort list — LeetCode 148	middle দিয়ে split (P1) → recurse → merge (P4)

Pattern cheat sheet¶

Pattern	Killer trigger	One-line essence
Slow/fast	"middle", "cycle"	speed ratio-ই position-এর তথ্য encode করে
Dummy head	head বদলাতে পারে	head-কে un-special বানাও
In-place reversal	"reverse", "O(1) space"	save → flip → advance, প্রতি step-এ এক node
Merge	"two sorted lists"	node re-thread করো, কখনো copy না
Runner	"nth from end, one pass"	gap-টাকে ruler হিসেবে বহন করো

এবার সবকিছু নিজে বানাও implementation.py-তে, তারপর tracker খোলো problems/README.md-তে।