Problem link ও উৎস
- **Original source:** Classic linked list exercise
- **Platform:** LeetCode —
- **Topic:** linked list
- **Difficulty:** Medium
- **Pattern:** middle + reverse + merge combo
- **Basic idea inherited from:** problem 1 (reverse), 2 (merge), 4 (middle) — তিনটা মিলিয়ে triple combo
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা singly linked list দেওয়া: `L0 -> L1 -> L2 -> ... -> Ln-1 -> Ln`। তোমাকে এটাকে **ভাঁজ করে** এই ক্রমে সাজাতে হবে:
```text
আগে : L0 -> L1 -> L2 -> ... -> Ln-1 -> Ln
পরে : L0 -> Ln -> L1 -> Ln-1 -> L2 -> ...
```
মানে — প্রথমটা, তারপর শেষেরটা, তারপর দ্বিতীয়টা, তারপর শেষের-আগেরটা... এভাবে দুই প্রান্ত থেকে ভেতরের দিকে। তুমি কেবল node-এর arrow বদলাবে, value নয়। কিছু return করতে হয় না — list-টা **in-place** বদলাও।
### Input ও output {#8-example-input-and-output}
```text
Input : 1 -> 2 -> 3 -> 4 -> Output: 1 -> 4 -> 2 -> 3
Input : 1 -> 2 -> 3 -> 4 -> 5 -> Output: 1 -> 5 -> 2 -> 4 -> 3
Edge 1 (একটা node): 1 -> Output: 1
Edge 2 (দুটো node): 1 -> 2 -> Output: 1 -> 2 (বদল নেই)
Edge 3 (খালি list): None -> Output: None
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
একতাড়া কাগজ ভাবো, ১ থেকে n নম্বর দেওয়া। তুমি চাও পড়ার ক্রম হোক: প্রথম পাতা, শেষ পাতা, দ্বিতীয় পাতা, শেষের-আগের পাতা... সহজ উপায়: তাড়াটা মাঝ থেকে দুই ভাগ করো, পিছনের ভাগটা **উল্টে** হাতে নাও, তারপর দুই হাত থেকে পালা করে একটা একটা পাতা নতুন তাড়ায় রাখো। ঠিক সেটাই এখানে করছি।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা একদম খাঁটি **combo** problem — আগের তিনটা skeleton একসাথে জোড়া:
- **Middle খোঁজা** (problem 4, [[004-middle-of-list.md](004-middle-of-list.md)](004-middle-of-list.md)) — slow/fast দিয়ে list-টা দুই ভাগে কাটার জন্য।
- **Reverse** (problem 1, [[001-reverse-linked-list.md](001-reverse-linked-list.md)](001-reverse-linked-list.md)) — দ্বিতীয় অর্ধটা উল্টে দেওয়ার জন্য।
- **Merge** (problem 2, [[002-merge-two-sorted-lists.md](002-merge-two-sorted-lists.md)](002-merge-two-sorted-lists.md)) — দুই অর্ধ পালা করে গেঁথে দেওয়ার জন্য (এখানে value তুলনা নয়, শুধু পালা করে)।
নতুন কিছু শিখতে হয় না; শুধু পুরোনো তিনটা যন্ত্র সঠিক ক্রমে চালাতে হয়।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic হলো একটা **symmetry**: চূড়ান্ত ক্রমে i-তম position-এ বসে পালা করে সামনের আর পিছনের node। যদি দ্বিতীয় অর্ধটা উল্টে ফেলি, তাহলে "পিছন থেকে আসা" node গুলো এখন একটা সাধারণ forward list হয়ে যায় — তখন দুই অর্ধ শুধু পালা করে interleave করলেই কাঙ্ক্ষিত ভাঁজ পাওয়া যায়। অর্থাৎ "শেষ থেকে নাও" সমস্যাটা "reverse করে সামনে থেকে নাও"-তে বদলে যায়।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
কোনো নতুন structure লাগে না — শুধু **কয়েকটা pointer** (slow, fast, prev, cur আর interleave করার সময় দুই অর্ধের head)। O(1) extra space-এই পুরো কাজ হয়।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Linked list-এ আমরা index করে শেষ থেকে node তুলতে পারি না (array-র মতো `L[n-i]` নেই)। কিন্তু **arrow ঘুরিয়ে দেওয়া** সস্তা — O(1)। তাই দ্বিতীয় অর্ধ reverse করে "পিছনের node গুলো সামনে আনা"-র কাজটা pointer দিয়েই হয়ে যায়, extra array না বানিয়ে। এটাই linked list-এ O(1) space-এ ভাঁজ করার সঠিক উপায়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
সরল চিন্তা: সব node-কে একটা **array**-তে রাখো (index করার সুবিধা পেতে)। তারপর দুই দিক থেকে দুটো index (`i=0`, `j=n-1`) নিয়ে পালা করে node তুলে নতুন arrow জোড়ো।
```text
[1, 2, 3, 4, 5]
i=0 → 1, j=4 → 5, i=1 → 2, j=3 → 4, i=2 → 3 (মাঝ)
জোড়ো: 1 -> 5 -> 2 -> 4 -> 3
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
কাজ করে, time-ও O(n), কিন্তু সব node-এর reference একটা array-তে রাখতে **O(n) extra space** লাগে। linked list-এর গোটা মজাই হলো arrow ঘুরিয়ে O(1) space-এ কাজ সারা। তাই array-তে সব তুলে ফেলা একরকম "linked list থাকার সুবিধা ফেলে দেওয়া"।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **"শেষ থেকে node তোলা" আসলে "দ্বিতীয় অর্ধ উল্টে সামনে থেকে তোলা"।** একবার দ্বিতীয় অর্ধ reverse হয়ে গেলে, সমস্যা দাঁড়ায় দুটো সাধারণ forward list-কে পালা করে গাঁথা — যেটা আমরা merge-এর সময় থেকেই পারি।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
তিন ধাপে ভাবো: (১) slow/fast দিয়ে middle খুঁজে list-টা দুই ভাগ করো, (২) দ্বিতীয় ভাগ reverse করো, (৩) দুই ভাগ থেকে পালা করে node নিয়ে arrow জোড়ো। প্রতিটা ধাপ একটা পরিচিত skeleton, আর প্রতিটাই O(n)/O(1)। মিলিয়ে এক পাসের মতো রৈখিক, কোনো extra array ছাড়াই।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "শেষ থেকে কীভাবে নেব" নিয়ে আটকে না থেকে list-টা মাঝখানে কেটে **পিছনের অর্ধ উল্টে দাও** — তখন কঠিন "শেষ থেকে তোলা" সমস্যাটা সহজ "দুটো forward list zip করা"-তে গলে যায়। বড় problem = তিনটা চেনা ছোট problem-এর সেলাই।
### ছবিতে বোঝা {#7-visual-explanation}
`1 -> 2 -> 3 -> 4 -> 5` দিয়ে তিন ধাপ:
```text
ধাপ ১ — middle-এ ভাঙো (slow শেষ first-half-এর):
first : 1 -> 2 -> 3
second : 4 -> 5
ধাপ ২ — second অর্ধ reverse করো:
first : 1 -> 2 -> 3
second : 5 -> 4
ধাপ ৩ — পালা করে interleave (প্রথম অংশ থেকে একটি, দ্বিতীয় অংশ থেকে একটি):
1 -> 5 -> 2 -> 4 -> 3
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `1 -> 2 -> 3 -> 4`:
1. Middle খোঁজো: `slow=2`, তাই `first = 1 -> 2`, `second = 3 -> 4`; `slow.next=None` দিয়ে কাটো।
2. `second` reverse করো → `4 -> 3`।
3. Interleave শুরু: `first=1`, `second=4`। `1.next=4`, `4.next=2` → `1 -> 4 -> 2 ...`; এখন `first=2`, `second=3`।
4. `2.next=3`, `3.next=None` → `1 -> 4 -> 2 -> 3`; `first=None`, `second=None`।
5. `second=None` → থামো। ফল: `1 -> 4 -> 2 -> 3`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reorder_list(head):
if not head or not head.next:
return head
# ১) middle খোঁজো — slow first-half-এর শেষে থামবে
slow = fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
second = slow.next # দ্বিতীয় অর্ধের শুরু
slow.next = None # দুই অর্ধ আলাদা করো
# ২) দ্বিতীয় অর্ধ reverse করো
prev = None
cur = second
while cur:
nxt = cur.next
cur.next = prev
prev = cur
cur = nxt
second = prev # উল্টানো দ্বিতীয় অর্ধের নতুন head
# ৩) দুই অর্ধ পালা করে interleave করো
first = head
while second:
f_nxt = first.next
s_nxt = second.next
first.next = second # first-এর পরে second-এর node
second.next = f_nxt # তার পরে first-এর পরের node
first = f_nxt
second = s_nxt
return head
# ---- 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(reorder_list(build([1, 2, 3, 4, 5]))) == [1, 5, 2, 4, 3]
assert to_list(reorder_list(build([1, 2, 3, 4]))) == [1, 4, 2, 3]
assert to_list(reorder_list(build([1]))) == [1]
assert to_list(reorder_list(build([1, 2]))) == [1, 2]
assert to_list(reorder_list(build([]))) == []
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `if not head or not head.next:` — খালি বা একক-node list-এ ভাঁজ করার কিছু নেই; যেমন আছে তেমন ফেরাও।
- `while fast.next and fast.next.next:` — এই শর্তে slow ঠিক **first-half-এর শেষ** node-এ থামে, তাই `slow.next` থেকে দ্বিতীয় অর্ধ শুরু।
- `second = slow.next; slow.next = None` — দুই অর্ধ আলাদা করো।
- reverse-loop (`prev`/`cur`/`nxt`) — problem 1-এর সেই তিন-pointer dance, দ্বিতীয় অর্ধে চালানো।
- interleave-loop — প্রতিবার দুই অর্ধের পরের node মনে রেখে (`f_nxt`, `s_nxt`) first→second→first ভাবে arrow জোড়া।
- `while second:` — দ্বিতীয় অর্ধ সবসময় সমান বা ছোট, তাই এটাকে শর্ত ধরলে ঠিক জায়গায় থামে।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`build([1,2,3,4,5])` → `1->2->3->4->5`। Middle ভেঙে `1->2->3` ও `4->5`; দ্বিতীয়টা reverse হয়ে `5->4`; interleave করে `1->5->2->4->3`, যা `to_list`-এ `[1,5,2,4,3]` — assert pass। জোড়-দৈর্ঘ্য, একক node, দুই node, খালি — সব pass হয়ে শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n)** — middle খোঁজা, reverse, আর interleave প্রতিটাই list-এর উপর একবার করে হাঁটা; মোট রৈখিক।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(1)** — শুধু কয়েকটা pointer; কোনো array বা নতুন node নয়, পুরোনো node-গুলোরই arrow ঘোরে।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- দুই অর্ধ আলাদা না করা (`slow.next = None` ভুলে যাওয়া) — তখন interleave-এ cycle তৈরি হয়ে infinite loop।
- Middle-এর শর্ত ভুল করা (`while fast and fast.next` বনাম `while fast.next and fast.next.next`) — first-half-এ ভুল node-এ থামলে জোড়/বিজোড়ে ভাঁজ এলোমেলো।
- Interleave-এ পরের node আগে না রাখা (`f_nxt`, `s_nxt`) — arrow বদলানোর পরে বাকি list হারিয়ে যায়।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি তিনটা: middle খোঁজা ([[004-middle-of-list.md](004-middle-of-list.md)](004-middle-of-list.md)), reverse ([[001-reverse-linked-list.md](001-reverse-linked-list.md)](001-reverse-linked-list.md)), merge ([[002-merge-two-sorted-lists.md](002-merge-two-sorted-lists.md)](002-merge-two-sorted-lists.md))। আটকে গেলে আগে এই তিনটা আলাদা করে ঝালিয়ে নাও — উত্তরের তিন-চতুর্থাংশ সেখানেই আছে।
### পরের অনুশীলন {#22-similar-harder-problems}
- Palindrome Linked List (middle + reverse-half combo) —