Skip to content

012 — Swap Nodes in Pairs

Source

  • 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, দ্বিগুণ করে

1. Problem in simple words

একটা 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

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 আলাদা করে ভাবতে হয় না।

6. Real-life analogy

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

7. Visual explanation

প্রতি জোড়ায় তিনটা 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

8. Example input and 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

9. Brute force thinking

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

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

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

15. Python solution

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।

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

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

21. Which basic problem this inherits from

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

22. Similar harder problems

23. Pattern learned

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

24. Final summary

ভবিষ্যতের আমাকে: "জোড়ায় জোড়ায় 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।