3.3 In-Place Reversal

Demo: Reverse Nodes in k-Group — LC 25 (Hard — Meta High)

Statement (Demo): linked list-এর head ও integer k দেওয়া — প্রতি kটা node-এর group reverse করুন। শেষে k-এর কম node বাকি থাকলে সেগুলো অপরিবর্তিত রাখুন। Modified list-এর head return করুন। উদাহরণ: head=[1,2,3,4,5], k=2 → [2,1,4,3,5] | ⚡ n ≤ 5000, 1 ≤ k ≤ n

Approach: আগে গুনে দেখুন k-টা নোড আছে কি না — না থাকলে ওই অংশ অপরিবর্তিত। থাকলে recursion দিয়ে পরের অংশ আগে সমাধান করুন, তারপর বর্তমান k-টা নোড standard reversal-এ উল্টে সেই ফলের সাথে জুড়ে দিন।

function reverseKGroup(head, k) {
  let count = 0,
    node = head;
  while (node && count < k) {
    node = node.next;
    count++;
  }
  if (count < k) return head; // k-এর কম বাকি → যেমন আছে
  let prev = reverseKGroup(node, k); // পরের গ্রুপ আগে সমাধান
  let cur = head;
  while (count--) {
    const next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
  }
  return prev;
}

Complexity: Time O(n), Space O(n/k) recursion (iterative করলে O(1))