Skip to content

020 — Reverse Nodes in k-Group

Source

  • Original source: Classic linked list exercise
  • Platform: LeetCode — https://leetcode.com/problems/reverse-nodes-in-k-group/
  • Topic: linked list
  • Difficulty: Hard
  • Pattern: segmented reversal + group counting
  • Basic idea inherited from: problem 13 (sublist reversal) একটা loop-এ, group counting সহ

1. Problem in simple words

একটা linked list আর একটা সংখ্যা k দেওয়া। তোমাকে list-টাকে পরপর k-টা node করে নিয়ে প্রতিটা group আলাদাভাবে reverse করতে হবে। শেষে যদি k-এর চেয়ে কম node পড়ে থাকে, সেগুলো যেমন আছে তেমন থাকবে (reverse হবে না)।

list : 1 -> 2 -> 3 -> 4 -> 5 ,  k = 2
ফল   : 2 -> 1 -> 4 -> 3 -> 5      (শেষের 5 একা, তাই অপরিবর্তিত)

k = 3 হলে:
ফল   : 3 -> 2 -> 1 -> 4 -> 5      (শেষের 4,5 দুটো, k-এর কম, অপরিবর্তিত)

2. Which basic idea does this inherit from?

ভিত্তি problem 13 (Reverse Linked List II — একটা অংশ reverse) আর problem 1-এর full reversal। সেখানে আমরা শিখেছি একটা নির্দিষ্ট segment কীভাবে উল্টে আবার বাকি list-এর সাথে সেলাই করতে হয়। এখানে সেটাই বারবার — পুরো list জুড়ে k-size segment করে, সাথে নতুন একটা শর্ত: group-এ k-টা node আছে কিনা আগে গুনে নেওয়া।

3. What is the hidden math or logic?

লুকানো logic: list-কে floor(n/k) টা পূর্ণ group আর শেষে একটা অসম্পূর্ণ অবশিষ্ট (n mod k node) হিসেবে দেখা। শুধু পূর্ণ group গুলো reverse হয়। প্রতিটা group reverse করার পরে দুটো সেলাই দরকার: group-এর নতুন head আগের অংশের সাথে, আর group-এর পুরোনো head (যা এখন লেজ) পরের অংশের সাথে। recursion এই সেলাই স্বয়ংক্রিয় করে দেয়।

4. Which data structure is needed?

কোনো নতুন structure লাগে না — শুধু কয়েকটা pointer (prev, cur, nxt) আর একটা counter (group-এ k node আছে কিনা গুনতে)। recursion ব্যবহার করলে call stack-এ O(n/k) depth।

5. Why this data structure fits

Linked list-এ একটা segment reverse করা মানে শুধু কিছু arrow ঘোরানো — O(1) extra (problem 1-এর তিন-pointer dance)। array হলে block-by-block উল্টে রাখতে সরানো-সরানি লাগত; এখানে শুধু link বদলালেই হয়। তাই pointer + counter-ই যথেষ্ট, আর recursion group-গুলোর মধ্যে সেলাইটা পরিষ্কার রাখে।

6. Real-life analogy

একসারি বই তাকে রাখা। তুমি প্রতি kটা বই করে নিয়ে সেই কটার ক্রম উল্টে দিচ্ছ, তারপর পরের k-টায় যাচ্ছ। কিন্তু একটা নিয়ম: একটা গুচ্ছ উল্টানোর আগে গুনে দেখো পুরো k-টা বই আছে কিনা — না থাকলে শেষের ওই কটা বই ছুঁয়ো না, যেমন আছে থাক।

7. Visual explanation

1 -> 2 -> 3 -> 4 -> 5, k = 2:

group 1: গুনে দেখো 2 node আছে (1,2) → reverse → 2 -> 1
group 2: গুনে দেখো 2 node আছে (3,4) → reverse → 4 -> 3
শেষ:     পড়ে আছে 5 — মাত্র 1 node (< k) → অপরিবর্তিত

সেলাই: (2 -> 1) -> (4 -> 3) -> 5
ফল  : 2 -> 1 -> 4 -> 3 -> 5

8. Example input and output

Input : 1 -> 2 -> 3 -> 4 -> 5 , k = 2   -> Output: 2 -> 1 -> 4 -> 3 -> 5
Input : 1 -> 2 -> 3 -> 4 -> 5 , k = 3   -> Output: 3 -> 2 -> 1 -> 4 -> 5

Edge 1 (k = 1):           1 -> 2 -> 3 , k=1  -> Output: 1 -> 2 -> 3 (বদল নেই)
Edge 2 (n, k-এর গুণিতক):   1->2->3->4 , k=2   -> Output: 2 -> 1 -> 4 -> 3
Edge 3 (একটা node):       1 , k=2            -> Output: 1
Edge 4 (খালি):            None , k=2         -> Output: None

9. Brute force thinking

সরল চিন্তা: সব value একটা array-তে তোলো। তারপর array-তে প্রতি k-size block আলাদা করে reverse করো (শেষ block-এ k-এর কম থাকলে ছেড়ে দাও), তারপর সেই value দিয়ে নতুন list বানাও বা পুরোনো node-এ বসাও।

[1,2,3,4,5], k=2
block reverse: [2,1, 4,3, 5] (শেষ 5 একা)
-> 2->1->4->3->5

10. Why brute force is slow

Time O(n) হলেও সব value array-তে তুলতে O(n) extra space লাগে — linked list-এ pointer ঘুরিয়ে in-place করলে যা লাগত না। Interview-তে আসল চ্যালেঞ্জ হলো extra array ছাড়া, শুধু arrow ঘুরিয়ে group-by-group reverse করা (O(1) extra, recursion বাদে)।

11. Key observation

মূল observation: একটা group reverse করার আগে নিশ্চিত হও সেখানে পুরো k-টা node আছে। k node আগে গুনে নিলে দুটো সুবিধা — (১) অসম্পূর্ণ শেষ group ভুলে reverse হয় না, (২) reverse-এর পরে পরের group-এর শুরু (গোনার সময় থেমে যাওয়া node) হাতেই থাকে, সেলাই সহজ হয়।

12. Optimized intuition

প্রতি group-এ: আগে k ঘর এগিয়ে গুনে দেখো k node আছে কিনা; না থাকলে এই অংশ যেমন আছে ফেরাও। থাকলে — বাকি list (k-তম node থেকে শুরু) recursively সমাধান করো, সেটার ফল হবে এই group-এর reversed অংশের পরের অংশ (prev)। তারপর এই k node-কে problem 1-এর dance দিয়ে reverse করো, প্রতিটার arrow পিছনের prev-এর দিকে ঘুরিয়ে। group-এর নতুন head ফেরাও।

13. Thinking tweak

মোচড়: "পুরো list একসাথে" না ভেবে ভাবো — "একটা group reverse করি, বাকিটার দায়িত্ব recursion-কে দিই।" আর reverse করার আগে k গুনে নাও — এই এক গোনা-ই অসম্পূর্ণ শেষ group-কে রক্ষা করে আর পরের group-এর শুরুটা হাতে এনে দেয়।

14. Step-by-step dry run

Input 1 -> 2 -> 3 -> 4 -> 5, k = 2:

  1. গুনো: 1, 2 — 2 node আছে; থামার পর node = 3।
  2. prev = reverse_k_group(3, 2) — recursion:
  3. গুনো 3, 4 — আছে; node = 5।
  4. prev = reverse_k_group(5, 2) → গুনে মাত্র 1 (< 2) → 5 ফেরাও।
  5. 3, 4 reverse, লেজ 3-এর পরে 5 জোড়া → 4 -> 3 -> 5; ফেরাও 4।
  6. এখন prev = 4 -> 3 -> 5; 1, 2 reverse, লেজ 1-এর পরে prev জোড়া → 2 -> 1 -> 4 -> 3 -> 5।
  7. ফেরাও 2। ফল: 2 -> 1 -> 4 -> 3 -> 5।

15. Python solution

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_k_group(head, k):
    # ১) সামনে k node আছে কিনা গুনো
    node = head
    count = 0
    while node and count < k:
        node = node.next
        count += 1
    if count < k:
        return head            # k-এর কম — যেমন আছে তেমন থাক

    # ২) বাকি অংশ আগে সমাধান করো (recursion); এটাই reversed group-এর পরের অংশ
    prev = reverse_k_group(node, k)

    # ৩) প্রথম k node reverse করো, arrow পিছনের prev-এর দিকে
    cur = head
    for _ in range(k):
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
    return prev                # group-এর নতুন 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(reverse_k_group(build([1, 2, 3, 4, 5]), 2)) == [2, 1, 4, 3, 5]
assert to_list(reverse_k_group(build([1, 2, 3, 4, 5]), 3)) == [3, 2, 1, 4, 5]
assert to_list(reverse_k_group(build([1, 2, 3, 4, 5]), 1)) == [1, 2, 3, 4, 5]
assert to_list(reverse_k_group(build([1, 2, 3, 4, 5, 6]), 3)) == [3, 2, 1, 6, 5, 4]
assert to_list(reverse_k_group(build([1]), 2)) == [1]
assert to_list(reverse_k_group(build([]), 2)) == []
print("সব test pass!")

16. Line-by-line code explanation

  • গোনা-loop (while node and count < k) — k ঘর এগিয়ে দেখো group-এ পুরো k node আছে কিনা; থামলে node = k-তম node (পরের group-এর শুরু)।
  • if count < k: return head — অসম্পূর্ণ শেষ group, অপরিবর্তিত ফেরাও।
  • prev = reverse_k_group(node, k) — বাকি list আগে সমাধান; এর ফলই হবে এই group-এর লেজের পরে জোড়া অংশ।
  • reverse-loop — problem 1-এর তিন-pointer dance, ঠিক k বার; প্রতিটা arrow পিছনের prev-এর দিকে ঘোরে, তাই group reverse হয়ে আপনাআপনি পরের অংশের সাথে সেলাই হয়।
  • return prev — k বার পরে prev = reversed group-এর নতুন head।

17. Output walkthrough

build([1,2,3,4,5]), k=2 → প্রথম group (1,2) reverse, বাকিটা recursion-এ (3,4) reverse আর 5 একা → 2->1->4->3->5 → [2,1,4,3,5] — assert pass। k=3, k=1, k-এর গুণিতক, একক node, খালি — সব pass; শেষে print: সব test pass!।

18. Time complexity

O(n) — প্রতিটা node-এ একবার গোনা হয় আর একবার reverse হয় (মোট ধ্রুবক-গুণ কাজ)। তাই রৈখিক।

19. Space complexity

O(n/k) — recursion stack প্রতি group-এ একবার গভীর হয়, মোট n/k level। (iterative লিখলে O(1)-এ নামানো যায়, কিন্তু সেলাই-pointer বেশি লাগে।)

20. Common mistakes

  • k গোনার আগেই reverse শুরু করা — তখন অসম্পূর্ণ শেষ group-ও ভুল করে উল্টে যায়।
  • reverse করার সময় group-এর লেজকে পরের অংশের সাথে জোড়াতে ভুলে যাওয়া — এখানে prev শুরুতেই recursion-এর ফল ধরায় সেলাই আপনিই হয়; না বুঝলে অংশ হারায়।
  • for _ in range(k)-এর বদলে value-শর্তে reverse করা — তখন কতগুলো node উল্টেছে তার হিসাব এলোমেলো।
  • খালি list বা k=1 আলাদা না ভাবা (যদিও এই code-এ এমনিতেই সঠিক)।

21. Which basic problem this inherits from

ভিত্তি: full reversal (001-reverse-linked-list.md) আর segment reversal (problem 13 — Reverse Linked List II)। এখানে সেই segment-reverse-কে group counting সহ পুরো list জুড়ে বারবার চালানো হয়েছে।

22. Similar harder problems

23. Pattern learned

Segmented reversal with counting: group-এ k node আছে কিনা আগে গুনে, তারপর সেই segment reverse করে recursion/loop-এ পরেরটার সাথে সেলাই — block-wise list rearrange-এর সাধারণ কৌশল।

24. Final summary

ভবিষ্যতের আমাকে: "k করে reverse? আগে k গুনো — পুরো group থাকলে reverse করো, বাকিটা recursion-কে দাও; না থাকলে অবশিষ্ট অংশ ছেড়ে দাও।" গোনা-আগে, উল্টানো-পরে — এটাই অসম্পূর্ণ শেষ group বাঁচানোর চাবি।

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