Reverse Nodes in k-Group

Problem Description
Given the head node head of a singly linked list and an integer k, you are required to reverse the nodes of the list k at a time. If the total number of nodes in the list is not a multiple of k, the remaining nodes at the end should maintain their original order. For example, for the list 1→2→3→4→5 and k=2, the reversed result is 2→1→4→3→5; for k=3, the result is 3→2→1→4→5.

Solution Approach
This problem can be broken down into two key steps:

1. Check if enough nodes remain for a group of k: If not, directly return the current section.
2. Reverse the current k nodes: Reverse the linked list segment within the interval through pointer manipulation, and recursively process the subsequent nodes.

Detailed Steps

Step 1: Define the reversal function (reverse nodes in interval [a, b))

• Goal: Reverse the linked list segment from node a to node b (exclusive of b), returning the new head node after reversal.
• Method: Use the iterative reversal method, maintaining three pointers: pre, cur, nxt.
  • Initialization: pre = null, cur = a.
  • Traverse until cur == b:
    • Save cur.next to nxt;
    • Set cur.next to point to pre;
    • Move pre and cur forward: pre = cur, cur = nxt.
  • Return pre (the new head node after reversal).

Step 2: Recursively process each group of k nodes

1. Check if enough nodes remain from the current head node for a group of k:
   • Set pointer p = head, traverse k times. If p == null is encountered midway, it indicates insufficient nodes, so directly return head (no reversal).
2. Reverse the current k nodes:
   • Call the reversal function to reverse the interval [head, p), obtaining the new head node newHead.
3. Recursively process the remaining linked list:
   • After reversing the current group, the original head node head becomes the tail node of the group. Set its next to point to the reversal result of the next group (i.e., the recursive call reverseKGroup(p, k)).
4. Return newHead.

Example Walkthrough (List 1→2→3→4→5, k=2)

1. First group:
   • Check the first 2 nodes (1→2), sufficient for reversal.
   • After reversal: 2→1. The next of the original head node 1 points to the result of the next group.
2. Second group:
   • Check nodes 3→4, sufficient for reversal.
   • After reversal: 4→3. The next of node 3 points to the remaining node 5.
3. Final result: 2→1→4→3→5.

Edge Case Handling

• If k=1, no reversal is needed, return the original list directly.
• If the list is empty or has only one node, return it directly.

Code Implementation (Reference)

def reverseKGroup(head, k):
    # Check if enough nodes remain for a group of k
    p = head
    for _ in range(k):
        if not p:
            return head
        p = p.next
    
    # Reverse the current k nodes
    new_head = reverse(head, p)
    # Recursively process subsequent groups and connect
    head.next = reverseKGroup(p, k)
    return new_head

def reverse(a, b):
    pre, cur = None, a
    while cur != b:
        nxt = cur.next
        cur.next = pre
        pre = cur
        cur = nxt
    return pre

Key Points Summary

• When reversing the interval [a, b), pay attention to the boundary condition (b is not included in the reversal).
• Ensure enough nodes remain for a group of k before recursion; otherwise, return directly.
• Time complexity is O(n), space complexity is O(n/k) (recursion stack depth).