# 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:**

```text
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](https://en.wikipedia.org/wiki/Cycle_detection)-এ।

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

**Representative problems:**

- Cycle detect করো — [LeetCode 141](https://leetcode.com/problems/linked-list-cycle/) — [Linked List Cycle: বাংলা নোট](problems/003-linked-list-cycle.md)
- Cycle-এর entry node খোঁজো — [LeetCode 142](https://leetcode.com/problems/linked-list-cycle-ii/) — [Linked List Cycle II: বাংলা নোট](problems/011-cycle-start.md)
- এক pass-এ middle — [LeetCode 876](https://leetcode.com/problems/middle-of-the-linked-list/) — [Middle of the Linked List: বাংলা নোট](problems/004-middle-of-list.md)

## 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 করো:**

```text
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](https://leetcode.com/problems/remove-linked-list-elements/) — [Remove Linked List Elements: বাংলা নোট](problems/006-remove-elements.md)
- দুটো sorted list merge করো — [LeetCode 21](https://leetcode.com/problems/merge-two-sorted-lists/) — [Merge Two Sorted Lists: বাংলা নোট](problems/002-merge-two-sorted-lists.md)
- শেষ থেকে nth সরাও (dummy + runner) — [LeetCode 19](https://leetcode.com/problems/remove-nth-node-from-end-of-list/) — [Remove Nth Node From End of List: বাংলা নোট](problems/009-remove-nth-from-end.md)

## 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 করো:**

```text
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](visual-explanation.md) section 4।)

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

**Representative problems:**

- পুরো list reverse করো — [LeetCode 206](https://leetcode.com/problems/reverse-linked-list/) — [Reverse Linked List: বাংলা নোট](problems/001-reverse-linked-list.md)
- দুটো position-এর মাঝের sublist reverse করো — [LeetCode 92](https://leetcode.com/problems/reverse-linked-list-ii/) — [Reverse Linked List II: বাংলা নোট](problems/013-reverse-sublist.md)
- k-group-এ reverse করো (hard) — [LeetCode 25](https://leetcode.com/problems/reverse-nodes-in-k-group/) — [Reverse Nodes in k-Group: বাংলা নোট](problems/020-reverse-k-group.md)

## 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 করো:**

```text
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:  dummy->1->2->3->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/](../02-arrays-and-strings/README.md), two-pointers pattern) প্লাস উপরের dummy-head pattern।

**Representative problems:**

- দুটো sorted list merge করো — [LeetCode 21](https://leetcode.com/problems/merge-two-sorted-lists/) — [Merge Two Sorted Lists: বাংলা নোট](problems/002-merge-two-sorted-lists.md)
- k-টা sorted list merge করো — [LeetCode 23](https://leetcode.com/problems/merge-k-sorted-lists/) — [Merge k Sorted Lists: বাংলা নোট](problems/019-merge-k-lists.md)
- একটা linked list O(n log n)-এ sort করো — [LeetCode 148](https://leetcode.com/problems/sort-list/) — [Sort List: বাংলা নোট](problems/017-sort-list.md)

## 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 করো:**

```text
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](https://leetcode.com/problems/remove-nth-node-from-end-of-list/) — [Remove Nth Node From End of List: বাংলা নোট](problems/009-remove-nth-from-end.md)
- দুটো list-এর intersection point — [LeetCode 160](https://leetcode.com/problems/intersection-of-two-linked-lists/) — [Intersection of Two Linked Lists: বাংলা নোট](problems/008-intersection-of-lists.md)
- List-কে ডানে k ঘুরাও — [LeetCode 61](https://leetcode.com/problems/rotate-list/) — [Rotate List: বাংলা নোট](problems/016-rotate-list.md)

---

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

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

| Problem | Recipe |
| --- | --- |
| Palindrome list, O(1) space — [LeetCode 234](https://leetcode.com/problems/palindrome-linked-list/) | middle (P1) → দ্বিতীয় অর্ধেক reverse (P3) → two-pointer compare |
| Reorder list — [LeetCode 143](https://leetcode.com/problems/reorder-list/) | middle (P1) → reverse (P3) → পালা করে merge (P4) |
| Sort list — [LeetCode 148](https://leetcode.com/problems/sort-list/) | 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](./implementation.py)-তে, তারপর tracker খোলো [problems/README.md](./problems/README.md)-তে।