কনটেন্টে যান

012 — Swap Nodes in Pairs

Problem link ও উৎস

  • Original source: Classic linked list exercise
  • Platform: LeetCode — https://leetcode.com/problems/swap-nodes-in-pairs/
  • Topic: linked list
  • Difficulty: Medium
  • Pattern: pointer rewiring + dummy head
  • Basic idea inherited from: insert-after-এর ordering rule, দ্বিগুণ করে

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

একটা linked list দেওয়া। পরপর প্রতি দুটো node-কে নিজেদের মধ্যে swap (অদলবদল) করো — মানে 1ম ও 2য়, 3য় ও 4র্থ, এভাবে। value বদলানো নয়, আসল node গুলোর arrow ঘুরিয়েই করতে হবে। নতুন head return করো।

উদাহরণ
আগে : 1 -> 2 -> 3 -> 4
পরে : 2 -> 1 -> 4 -> 3

বিজোড় হলে শেষেরটা একা থাকে:
আগে : 1 -> 2 -> 3
পরে : 2 -> 1 -> 3

Input ও output

উদাহরণ
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

চেনা উদাহরণে বোঝা

লাইনে দাঁড়ানো মানুষজন জোড়ায় জোড়ায় জায়গা বদল করছে — সামনের দুজন নিজেদের মধ্যে, তারপর পরের দুজন, এভাবে। কিন্তু বদলের আগে খেয়াল রাখতে হয় পিছনের লোকের হাত যেন নতুন সামনের জনের হাত ধরে — নাহলে লাইনের পেছনের অংশটা ছিটকে যায়।

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

এর ভিত্তি pointer rewiring — কোন arrow আগে, কোনটা পরে সেট করলে কোনো node হারায় না, সেই ordering discipline। insert-after / delete operation-এ আমরা যে সাবধানে arrow সাজাই, এখানে সেটাই দুটো node-এর জন্য একসাথে — তাই "ordering rule, দ্বিগুণ করে"। সাথে problem 2-এর dummy head কৌশল, যাতে প্রথম জোড়া swap করার পরও head ঠিক থাকে।

ভেতরের যুক্তি

কোনো গভীর অঙ্ক নয় — একটা local rewiring invariant। প্রতি জোড়া (a, b)-এর জন্য তিনটা arrow সঠিক ক্রমে সেট করতে হয়: a.next = b.next (a পরের জোড়ার দিকে তাকাবে), b.next = a (b এখন a-এর আগে), আর আগের অংশের শেষ node b-এর দিকে। ক্রমটা ভুল হলে list-এর লেজ হারিয়ে যায়।

কী দিয়ে তথ্য রাখব

কোনো extra structure নয় — একটা dummy head + একটা prev pointer। dummy থাকায় প্রথম জোড়া swap করলেও নতুন head (= আসল ২য় node) সহজে ফেরানো যায়।

এটি কেন উপযুক্ত

Linked list-এ swap মানে শুধু কয়েকটা arrow ঘোরানো — O(1), কোনো data সরানো লাগে না। prev সবসময় এক-জোড়ার ঠিক আগের node ধরে রাখে, তাই নতুন জোড়ার মাথা (b) তার সাথে জোড়া যায়। dummy head থাকায় "প্রথম node বদলে যাবে" সেই special case আলাদা করে ভাবতে হয় না।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

সরল চিন্তা: list-এর সব value একটা array-তে নাও, array-তে জোড়ায় জোড়ায় swap করো ([i] ও [i+1]), তারপর সেই array দিয়ে নতুন list বানাও — বা পুরোনো node গুলোর value সোজা বসিয়ে দাও।

উদাহরণ
[1,2,3,4] -> জোড়া swap -> [2,1,4,3] -> নতুন list

কোথায় বেশি কাজ হচ্ছে

কাজ করে, কিন্তু value-copy করা মানে problem-এর আসল চ্যালেঞ্জটা এড়িয়ে যাওয়া (অনেক ক্ষেত্রে value-অদলবদল নিষিদ্ধ — node-ই swap করতে হবে)। array নিলে O(n) extra space-ও লাগে। arrow rewiring করলে পুরোনো node গুলোই reuse হয়, O(1) space-এ।

যে বিষয়টি খেয়াল করতে হবে

মূল observation: পুরো list নিয়ে না ভেবে একটা জোড়ায় মন দাও — তিনটা arrow সঠিক ক্রমে সেট করলেই সেই জোড়া swap হয়ে যায়, আর prev পরের জোড়ার জন্য তৈরি থাকে। বাকিটা একই কাজের পুনরাবৃত্তি।

আরও কম কাজে সমাধান

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।

ভাবনার পরিবর্তন

মোচড়: "সব swap করব" না ভেবে ভাবো — "একটা জোড়ার তিনটা arrow সঠিক ক্রমে বাঁধি, prev কে জোড়ার লেজে রেখে দিই; বাকিটা loop।" ক্রমটাই আসল: a পরের জোড়ার দিকে → b তে a → prev তে b।

ছবিতে বোঝা

প্রতি জোড়ায় তিনটা arrow নতুন করে বাঁধা। 1 -> 2 -> 3 -> 4, prev = dummy:

উদাহরণ
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-এ ধাপে ধাপে

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

কোড ও ব্যাখ্যা

Python

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!")

কোডের প্রতিটি অংশ

  • 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 মিলিয়ে দেখা

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!।

খরচ ও সাধারণ ভুল

সময়

O(n) — প্রতিটা node ঠিক একবার করে দেখা/rewire হয়; list-এর উপর এক পাস।

অতিরিক্ত জায়গা

O(1) — শুধু dummy + কয়েকটা pointer; পুরোনো node reuse হয়, extra memory বাড়ে না। (recursive version লিখলে call stack-এ O(n) লাগত।)

যে ভুলগুলো এড়াতে হবে

  • 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) এটা ঠেকায়।

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

ভিত্তি: pointer rewiring discipline (insert/delete-এর arrow ordering, ../operations.md) আর problem 2 ([002-merge-two-sorted-lists.md](002-merge-two-sorted-lists.md))-এর dummy head কৌশল।

পরের অনুশীলন

কৌশলটি মনে রাখুন

Pairwise rewiring with dummy: dummy + prev ধরে রেখে প্রতি জোড়ার তিনটা arrow সঠিক ক্রমে ঘোরাও; এক পাসে, O(1) space-এ node-level swap।

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে: "জোড়ায় জোড়ায় swap? value নয়, arrow ঘোরাও — dummy + prev নাও; প্রতি জোড়ায় a.next→পরের জোড়া, b.next→a, prev.next→b, তারপর prev=a।" ক্রম ভুল করলেই লেজ হারাবে।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।