Problem link ও উৎস
- **Original source:** Classic linked list exercise
- **Platform:** LeetCode —
- **Topic:** linked list
- **Difficulty:** Medium
- **Pattern:** merge sort on chains
- **Basic idea inherited from:** middle দিয়ে split (problem 4) + merge two (problem 2), recursively
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা linked list দেওয়া, যার value গুলো এলোমেলো। তোমাকে এটাকে **ছোট-থেকে-বড় (ascending)** ক্রমে sort করতে হবে আর sorted list-এর head return করতে হবে। লক্ষ্য: **O(n log n)** সময়ে — মানে সহজ O(n²) sort চলবে না।
```text
আগে : 4 -> 2 -> 1 -> 3
পরে : 1 -> 2 -> 3 -> 4
```
### Input ও output {#8-example-input-and-output}
```text
Input : 4 -> 2 -> 1 -> 3 -> Output: 1 -> 2 -> 3 -> 4
Input : -1 -> 5 -> 3 -> 4 -> 0 -> Output: -1 -> 0 -> 3 -> 4 -> 5
Edge 1 (খালি list): None -> Output: None
Edge 2 (একটা node): 1 -> Output: 1
Edge 3 (duplicate): 3 -> 3 -> 1 -> Output: 1 -> 3 -> 3
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
একগাদা পরীক্ষার খাতা sort করছ। একা পুরোটা সামলানো কঠিন, তাই তাড়াটা **অর্ধেক অর্ধেক** করে ভাগ করে দুজনকে দিলে; তারা আবার ভাগ করল — যতক্ষণ না হাতে এক-একটা খাতা থাকে (এমনিতেই sorted)। তারপর দুজন দুজন মিলে দুটো sorted তাড়া এক করে উপরে উঠতে থাকল — শেষে পুরোটা sorted।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা দুটো পুরোনো skeleton recursively জোড়া — খাঁটি **merge sort**, কিন্তু array নয়, linked list-এ:
- **Middle দিয়ে split** (problem 4, [[004-middle-of-list.md](004-middle-of-list.md)](004-middle-of-list.md)) — list-টা মাঝখান থেকে দুই ভাগ করা।
- **Merge two sorted lists** (problem 2, [[002-merge-two-sorted-lists.md](002-merge-two-sorted-lists.md)](002-merge-two-sorted-lists.md)) — দুই sorted অর্ধ জোড়া দেওয়া।
দুটোকে recursion-এ মুড়ে দিলেই পুরো sort।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic হলো **divide and conquer**-এর সেই recurrence: `T(n) = 2·T(n/2) + O(n)`। প্রতি level-এ পুরো n node merge হয় (O(n)), আর প্রতিবার অর্ধেক করে ভাঙায় level-এর সংখ্যা log n। তাই মোট **O(n log n)**। merge sort তাই array-র মতো linked list-এও সমান দক্ষ — বরং linked list-এ merge step-এ extra space লাগে না।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
কোনো নতুন container নয় — list নিজেই যথেষ্ট। লাগে slow/fast **pointer** (split-এর জন্য), dummy head (merge-এর জন্য), আর recursion-এর জন্য **call stack**। তাই extra space মূলত recursion depth = O(log n)।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Merge sort-এর জন্য linked list আদর্শ: array merge-এ দুই অর্ধ জোড়াতে O(n) extra array লাগে, কিন্তু linked list-এ merge শুধু **arrow ঘোরানো** — O(1) extra (recursion stack বাদে)। আর random access না থাকায় quicksort-এর pivot ভাগ ঝামেলার; তাই linked list-এ **merge sort**-ই স্বাভাবিক পছন্দ।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
সরল চিন্তা: সব value একটা **array**-তে তুলে নাও, array-টা sort করো (`sorted()`), তারপর sorted value দিয়ে নতুন list বানাও বা পুরোনো node-এ value বসাও।
```text
4->2->1->3 -> [4,2,1,3] -> sort -> [1,2,3,4] -> 1->2->3->4
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
আসলে এটা O(n log n) time দেয় (Python-এর sort), কিন্তু **O(n) extra space** নেয় (array)। আর এটা linked list-এর কাঠামোকে কাজে লাগায় না — node-এর arrow ঘুরিয়ে in-place merge করলে extra array লাগত না। Interview-তে চাওয়া হয় list-এর উপরেই merge sort, যাতে extra space কমে (শুধু recursion stack)।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **একটা একক node সবসময় sorted।** তাই list-কে বারবার অর্ধেক করে ভাঙতে থাকো যতক্ষণ না প্রতিটা টুকরো এক-node হয় (তখন এমনিতেই sorted), তারপর জোড়ায় জোড়ায় merge করে উপরে ওঠো — এটাই merge sort-এর প্রাণ।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
Recursion-এ ভাবো: base case — list খালি বা এক-node হলে already sorted, ফেরাও। নাহলে slow/fast দিয়ে middle খুঁজে দুই ভাগে কাটো, দুই ভাগকে recursively sort করো, তারপর problem 2-এর merge দিয়ে দুই sorted অর্ধ জোড়ো। উপরে উঠতে উঠতে পুরো list sorted।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "পুরো list কীভাবে sort করব" না ভেবে ভাবো — "অর্ধেক করে কেটে দুজনকে দিয়ে দিই; ওরা sorted করে আনলে আমি শুধু দুটো sorted জিনিস merge করব।" বড় কাজটা নিজেকে সমর্পণ করে দাও recursion-এর হাতে; তোমার দায়িত্ব শুধু split আর merge।
### ছবিতে বোঝা {#7-visual-explanation}
`4 -> 2 -> 1 -> 3` দিয়ে split-merge গাছ:
```text
[4, 2, 1, 3]
split (middle)
/ \
[4, 2] [1, 3]
/ \ / \
[4] [2] [1] [3]
\ / \ /
merge → [2, 4] merge → [1, 3]
\ /
merge → [1, 2, 3, 4]
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `4 -> 2 -> 1 -> 3`:
1. split (slow=`head`, fast=`head.next`): slow node 2-এ থামে → `left = 4 -> 2`, `right = 1 -> 3`।
2. `sort(4 -> 2)`: আবার split → `[4]`, `[2]`; merge → `2 -> 4`।
3. `sort(1 -> 3)`: split → `[1]`, `[3]`; merge → `1 -> 3`।
4. উপরে merge: `merge(2 -> 4, 1 -> 3)` → দুই মাথা তুলনা করে `1 -> 2 -> 3 -> 4`।
5. ফল: `1 -> 2 -> 3 -> 4`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def merge_two(l1, l2):
dummy = ListNode() # dummy head — head-এর special case এড়াতে
tail = dummy
while l1 and l2:
if l1.val <= l2.val:
tail.next = l1
l1 = l1.next
else:
tail.next = l2
l2 = l2.next
tail = tail.next
tail.next = l1 if l1 else l2 # যেটা বাকি, পুরো জুড়ে দাও
return dummy.next
def sort_list(head):
if not head or not head.next:
return head # খালি বা এক-node → already sorted
# split: middle খোঁজো (fast = head.next দিয়ে দুই-node case-ও এগোয়)
slow = head
fast = head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
mid = slow.next # দ্বিতীয় অর্ধের শুরু
slow.next = None # দুই অর্ধ আলাদা করো
left = sort_list(head) # দুই অর্ধ recursively sort
right = sort_list(mid)
return merge_two(left, right)
# ---- 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
# ---- tests ----
assert to_list(sort_list(build([4, 2, 1, 3]))) == [1, 2, 3, 4]
assert to_list(sort_list(build([-1, 5, 3, 4, 0]))) == [-1, 0, 3, 4, 5]
assert to_list(sort_list(build([]))) == []
assert to_list(sort_list(build([1]))) == [1]
assert to_list(sort_list(build([2, 1]))) == [1, 2]
assert to_list(sort_list(build([3, 3, 1, 1, 2]))) == [1, 1, 2, 3, 3]
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `if not head or not head.next:` — base case: খালি বা এক-node already sorted।
- `slow = head; fast = head.next` — split-এ এখানে fast এক ঘর এগিয়ে শুরু; এতে দুই-node list-এ slow প্রথম node-এ থামে, যাতে দুই অর্ধই non-empty হয় (নাহলে infinite recursion)।
- `while fast and fast.next:` — slow ঠিক first-half-এর শেষে থামবে।
- `mid = slow.next; slow.next = None` — list দুই ভাগ।
- `left = sort_list(head); right = sort_list(mid)` — recursively দুই অর্ধ sort।
- `merge_two(left, right)` — problem 2-এর merge: দুই sorted অর্ধ এক করো।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`build([4,2,1,3])` → `4->2->1->3`। split → `4->2` ও `1->3`; recursively sort → `2->4` ও `1->3`; merge → `1->2->3->4` → `[1,2,3,4]` — assert pass। নেগেটিভ, খালি, এক-node, দুই-node, duplicate — সব pass হয়ে শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n log n)** — প্রতি level-এ সব মিলিয়ে O(n) merge কাজ, আর অর্ধেক করে ভাঙায় log n level; গুণ করলে n log n।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(log n)** — merge নিজে O(1) (arrow ঘোরায়), কিন্তু recursion stack-এর গভীরতা log n। (পুরো iterative bottom-up লিখলে O(1)-এ নামানো যায়।)
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- split-এ `fast = head` রাখা (`head.next`-এর বদলে) — দুই-node list-এ এক অর্ধ খালি থেকে যায় → infinite recursion / stack overflow।
- `slow.next = None` দিয়ে দুই অর্ধ আলাদা করতে ভুলে যাওয়া — তখন merge-এ overlap, ভুল ফল বা loop।
- base case (খালি/এক-node) না দেওয়া — recursion কখনো থামে না।
- merge-এ `<` ব্যবহার করা `<=`-এর বদলে — duplicate-এ stable order হারাতে পারে।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি দুটো: middle দিয়ে split ([[004-middle-of-list.md](004-middle-of-list.md)](004-middle-of-list.md)) আর merge two sorted lists ([[002-merge-two-sorted-lists.md](002-merge-two-sorted-lists.md)](002-merge-two-sorted-lists.md))। আটকে গেলে আগে এই দুটো আলাদা করে ঝালিয়ে নাও — sort তাদেরই recursion-এ মোড়ানো রূপ।
### পরের অনুশীলন {#22-similar-harder-problems}
- Merge k Sorted Lists —