Iterative Block Reversal with Tail Reconnection (O(n) Time | O(1) Space)#

LeetCode #25 | Difficulty: Hard

Intuition#

The problem asks us to reverse nodes in groups of size k.

Instead of reversing the entire list at once, we can think in terms of independent blocks of size k:

• If a block has exactly k nodes → reverse it.
• If fewer than k nodes remain → leave them as it is.

So the problem reduces to repeating three operations:

1. Check if k nodes exist.
2. Reverse exactly k nodes.
3. Reconnect the reversed block with the previous and next parts.

The key challenge is handling pointer connections correctly between groups.

Approach#

1. Maintain:

   • head → start of current group.
   • cur → used to check if k nodes exist.
   • newHead → head of final modified list.
   • kTail → tail of previously reversed group.

2. For each group:

   • Move cur forward k steps to check if k nodes are available.
   • If count == k:
     • Reverse the k nodes using helper reverseLL.
     • If this is the first reversed group, update newHead.
     • Connect previous group’s tail (kTail) to the reversed head.
     • Update kTail to current group’s original head (which becomes tail after reversal).
     • Move head forward to the next group start.

3. If fewer than k nodes remain:

   • Attach remaining nodes as-is.

4. Return:

   • newHead if at least one reversal happened.
   • Otherwise original head.

Helper Function#

reverseLL(head, k):

• Iteratively reverses exactly k nodes.
• Uses standard 3-pointer technique.
• Returns new head of reversed block.

Complexity#

• Time complexity: O(n)

  Each node is visited a constant number of times. Every node participates in exactly one reversal.

• Space complexity: O(1)

  Only a few pointer variables are used. No recursion or extra data structures.

Code#

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseLL(ListNode* head, int k) {
        ListNode* cur = head;
        ListNode* pre = nullptr;
        while(k>0) {
            ListNode* temp = cur;
            cur = cur->next;
            temp->next = pre;
            pre = temp;
            k--;
        }
        return pre;
    }

    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* cur = head;
        ListNode* newHead = nullptr;
        ListNode* kTail = nullptr;
        while(cur) {
            int count = 0;
            cur = head;
            while(count<k && cur) {
                cur = cur->next;
                count++;
            }
            if(count==k) {
                ListNode* revHead = reverseLL(head, k);
                if(newHead == nullptr) newHead = revHead;
                if(kTail!=nullptr) kTail->next = revHead;
                kTail = head;
                head = cur;
            }
        }
        if(kTail!=nullptr) kTail->next = head;
        return (newHead==nullptr) ? head : newHead;
    }
};

---