Problem link ও উৎস
- **Original source:** Classic linked list exercise
- **Platform:** LeetCode —
- **Topic:** linked list
- **Difficulty:** Medium
- **Pattern:** pointer rewiring + dummy head
- **Basic idea inherited from:** insert-after-এর ordering rule, দ্বিগুণ করে
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা linked list দেওয়া। পরপর প্রতি **দুটো** node-কে নিজেদের মধ্যে swap (অদলবদল) করো — মানে 1ম ও 2য়, 3য় ও 4র্থ, এভাবে। **value বদলানো নয়**, আসল node গুলোর arrow ঘুরিয়েই করতে হবে। নতুন head return করো।
```text
আগে : 1 -> 2 -> 3 -> 4
পরে : 2 -> 1 -> 4 -> 3
বিজোড় হলে শেষেরটা একা থাকে:
আগে : 1 -> 2 -> 3
পরে : 2 -> 1 -> 3
```
### Input ও output {#8-example-input-and-output}
```text
Input : 1 -> 2 -> 3 -> 4 -> Output: 2 -> 1 -> 4 -> 3
Input : 1 -> 2 -> 3 -> Output: 2 -> 1 -> 3 (বিজোড়: শেষটা একা)
Edge 1 (একটা node): 1 -> Output: 1
Edge 2 (খালি list): None -> Output: None
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
লাইনে দাঁড়ানো মানুষজন জোড়ায় জোড়ায় জায়গা বদল করছে — সামনের দুজন নিজেদের মধ্যে, তারপর পরের দুজন, এভাবে। কিন্তু বদলের আগে খেয়াল রাখতে হয় পিছনের লোকের হাত যেন নতুন সামনের জনের হাত ধরে — নাহলে লাইনের পেছনের অংশটা ছিটকে যায়।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এর ভিত্তি **pointer rewiring** — কোন arrow আগে, কোনটা পরে সেট করলে কোনো node হারায় না, সেই ordering discipline। insert-after / delete operation-এ আমরা যে সাবধানে arrow সাজাই, এখানে সেটাই দুটো node-এর জন্য একসাথে — তাই "ordering rule, দ্বিগুণ করে"। সাথে problem 2-এর **dummy head** কৌশল, যাতে প্রথম জোড়া swap করার পরও head ঠিক থাকে।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
কোনো গভীর অঙ্ক নয় — একটা **local rewiring invariant**। প্রতি জোড়া `(a, b)`-এর জন্য তিনটা arrow সঠিক ক্রমে সেট করতে হয়: `a.next = b.next` (a পরের জোড়ার দিকে তাকাবে), `b.next = a` (b এখন a-এর আগে), আর আগের অংশের শেষ node `b`-এর দিকে। ক্রমটা ভুল হলে list-এর লেজ হারিয়ে যায়।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
কোনো extra structure নয় — একটা **dummy head** + একটা `prev` pointer। dummy থাকায় প্রথম জোড়া swap করলেও নতুন head (= আসল ২য় node) সহজে ফেরানো যায়।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Linked list-এ swap মানে শুধু কয়েকটা arrow ঘোরানো — O(1), কোনো data সরানো লাগে না। `prev` সবসময় এক-জোড়ার ঠিক আগের node ধরে রাখে, তাই নতুন জোড়ার মাথা (`b`) তার সাথে জোড়া যায়। dummy head থাকায় "প্রথম node বদলে যাবে" সেই special case আলাদা করে ভাবতে হয় না।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
সরল চিন্তা: list-এর সব value একটা array-তে নাও, array-তে জোড়ায় জোড়ায় swap করো (`[i]` ও `[i+1]`), তারপর সেই array দিয়ে নতুন list বানাও — বা পুরোনো node গুলোর value সোজা বসিয়ে দাও।
```text
[1,2,3,4] -> জোড়া swap -> [2,1,4,3] -> নতুন list
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
কাজ করে, কিন্তু value-copy করা মানে problem-এর আসল চ্যালেঞ্জটা এড়িয়ে যাওয়া (অনেক ক্ষেত্রে value-অদলবদল নিষিদ্ধ — node-ই swap করতে হবে)। array নিলে O(n) extra space-ও লাগে। arrow rewiring করলে পুরোনো node গুলোই reuse হয়, O(1) space-এ।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: পুরো list নিয়ে না ভেবে **একটা জোড়ায়** মন দাও — তিনটা arrow সঠিক ক্রমে সেট করলেই সেই জোড়া swap হয়ে যায়, আর `prev` পরের জোড়ার জন্য তৈরি থাকে। বাকিটা একই কাজের পুনরাবৃত্তি।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
dummy বসাও, `prev = dummy`। যতক্ষণ `prev.next` আর `prev.next.next` দুটোই আছে (মানে একটা পুরো জোড়া আছে): `a = prev.next`, `b = a.next`; `a.next = b.next`, `b.next = a`, `prev.next = b`; তারপর `prev = a` (এখন জোড়ার শেষে)। শেষে `dummy.next`।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "সব swap করব" না ভেবে ভাবো — "একটা জোড়ার তিনটা arrow সঠিক ক্রমে বাঁধি, `prev` কে জোড়ার লেজে রেখে দিই; বাকিটা loop।" ক্রমটাই আসল: a পরের জোড়ার দিকে → b তে a → prev তে b।
### ছবিতে বোঝা {#7-visual-explanation}
প্রতি জোড়ায় তিনটা arrow নতুন করে বাঁধা। `1 -> 2 -> 3 -> 4`, `prev = dummy`:
```text
dummy -> 1 -> 2 -> 3 -> 4 , a=1, b=2
a.next = b.next → 1 -> 3 (a পরের জোড়ার দিকে)
b.next = a → 2 -> 1
prev.next = b → dummy -> 2 -> 1 -> 3 -> 4
prev = a (=1) → prev এখন জোড়ার শেষে
পরের জোড়া a=3, b=4 একইভাবে:
dummy -> 2 -> 1 -> 4 -> 3
return dummy.next = 2 -> 1 -> 4 -> 3
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `1 -> 2 -> 3 -> 4`:
1. `dummy -> 1 -> 2 -> 3 -> 4`; `prev = dummy`
2. জোড়া: `a = 1`, `b = 2`; `a.next = b.next (=3)`; `b.next = a`; `prev.next = b` → `dummy -> 2 -> 1 -> 3 -> 4`; `prev = a (=1)`
3. জোড়া: `a = 3`, `b = 4`; `a.next = b.next (=None)`; `b.next = a`; `prev.next = b` → `dummy -> 2 -> 1 -> 4 -> 3`; `prev = a (=3)`
4. `prev.next = None` → loop শেষ
5. return `dummy.next` = `2 -> 1 -> 4 -> 3`
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def swap_pairs(head):
dummy = ListNode(0, head) # head বদলালেও যাতে সহজে ফেরানো যায়
prev = dummy
while prev.next and prev.next.next: # একটা পুরো জোড়া আছে কি না
a = prev.next # জোড়ার প্রথম
b = a.next # জোড়ার দ্বিতীয়
a.next = b.next # a পরের জোড়ার দিকে তাকাও
b.next = a # b এখন a-এর আগে
prev.next = b # আগের অংশ নতুন মাথা b-তে জোড়ো
prev = a # prev জোড়ার শেষে সরাও
return dummy.next
# ---- 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(swap_pairs(build([1, 2, 3, 4]))) == [2, 1, 4, 3]
assert to_list(swap_pairs(build([1, 2, 3]))) == [2, 1, 3] # বিজোড়: শেষটা একা
assert to_list(swap_pairs(build([1]))) == [1] # একটা node
assert to_list(swap_pairs(build([]))) == [] # খালি
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `dummy = ListNode(0, head)` — নকল head; প্রথম জোড়া swap করলেও নতুন head সহজে ফেরে।
- `prev = dummy` — `prev` সবসময় বর্তমান জোড়ার ঠিক আগে।
- `while prev.next and prev.next.next:` — সামনে একটা পুরো জোড়া (দুটো node) আছে কি না।
- `a = prev.next; b = a.next` — জোড়ার দুই node।
- `a.next = b.next` — `a` পরের জোড়ার দিকে তাকায় (লেজ হারায় না)।
- `b.next = a` — `b` এখন `a`-এর আগে — swap সম্পন্ন।
- `prev.next = b` — আগের অংশকে নতুন মাথা `b`-তে জোড়ো।
- `prev = a` — `prev` জোড়ার শেষ node-এ; পরের জোড়ার জন্য তৈরি।
- `return dummy.next` — আসল নতুন head।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`build([1,2,3,4])` বানায় `1->2->3->4`; দুই জোড়া swap হয়ে `[2,1,4,3]`। `[1,2,3]`-এ প্রথম জোড়া swap, শেষ `3` একা → `[2,1,3]`। একক node ও খালি অপরিবর্তিত। সব assert pass → `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n)** — প্রতিটা node ঠিক একবার করে দেখা/rewire হয়; list-এর উপর এক পাস।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(1)** — শুধু dummy + কয়েকটা pointer; পুরোনো node reuse হয়, extra memory বাড়ে না। (recursive version লিখলে call stack-এ O(n) লাগত।)
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- arrow তিনটা ভুল ক্রমে সেট করা — যেমন `prev.next = b`-এর আগে `a.next = b.next` না করলে পরের জোড়া হারিয়ে যায়।
- `prev = a`-এর বদলে `prev = b` করা — `b` এখন জোড়ার মাথা, লেজ নয়; pointer ভুল জায়গায় যায়।
- dummy head না নিয়ে head আলাদা করে সামলানো — code জটিল ও bug-প্রবণ।
- বিজোড় দৈর্ঘ্যে শেষ একক node ভুলে swap করতে যাওয়া — `while`-এর দ্বিতীয় শর্ত (`prev.next.next`) এটা ঠেকায়।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: pointer rewiring discipline (insert/delete-এর arrow ordering, [../operations.md](../operations.md)) আর problem 2 ([[002-merge-two-sorted-lists.md](002-merge-two-sorted-lists.md)](002-merge-two-sorted-lists.md))-এর dummy head কৌশল।
### পরের অনুশীলন {#22-similar-harder-problems}
- Reverse Nodes in k-Group (জোড়ার বদলে k-গ্রুপ) —