Leetcode 25. Reverse Nodes in k-Group

Problem

You are given the head of a singly linked list and an integer k. Your task is to reverse every group of k consecutive nodes in the list. If the number of remaining nodes at the end is less than k, those nodes should remain in their original order.

You must solve this problem by modifying the links in the linked list directly, and your solution should use O(1) extra memory (aside from the recursion stack if using recursion).

Requirements

1. Reverse nodes in groups of exactly k nodes at a time
2. If fewer than k nodes remain at the end, leave them unchanged
3. Use O(1) extra space (not counting recursion stack)
4. Only modify the node pointers, do not modify node values

Constraints

• The number of nodes in the list is in the range [1, 5000]
• 1 <= k <= 5000
• 0 <= Node.val <= 1000

Examples

Example 1:

` Input: head = [1,2,3,4,5], k = 2 Output: [2,1,4,3,5] Explanation:

• Nodes 1->2 are reversed to 2->1
• Nodes 3->4 are reversed to 4->3
• Node 5 remains as-is (incomplete group) `

Example 2:

` Input: head = [1,2,3,4,5], k = 3 Output: [3,2,1,4,5] Explanation:

• Nodes 1->2->3 are reversed to 3->2->1
• Nodes 4->5 remain unchanged (only 2 nodes, less than k=3) `

Example 3:

Input: head = [1,2,3,4,5], k = 1 Output: [1,2,3,4,5] Explanation: With k=1, each group has 1 node, so no reversal occurs.

Example 4:

Input: head = [1], k = 1 Output: [1] Explanation: Single node remains unchanged.

Hint 1: Counting Nodes Before reversing a group, you need to check if there are at least k nodes remaining. Traverse ahead to count available nodes before starting the reversal.

Hint 2: Reversal Pattern To reverse a segment of a linked list, you'll need to track three pointers: the previous node, the current node, and the next node. Process one group at a time and connect the reversed group back to the main list.

Hint 3: Connection Points Pay special attention to connecting the tail of a reversed group to the head of the next group (or remaining nodes). Also consider using a dummy node at the beginning to handle edge cases more easily.

Full Solution `` Explanation:

The solution uses a three-step approach for each group:

1. Check availability: Before reversing, we verify that at least k nodes are available from the current position. If not, we leave the remaining nodes unchanged.
2. Reverse the group: We reverse exactly k nodes using the standard linked list reversal technique with three pointers (prev, curr, next). This returns the new head of the reversed segment and the first node of the next segment.
3. Reconnect: We connect the tail of the previous group to the new head of the current (reversed) group, and connect the tail of the current group to the start of the next segment.

A dummy node simplifies handling the very first group, as we don't need special logic for the head of the list.

Time Complexity: O(n) where n is the number of nodes. We visit each node at most twice (once for counting, once for reversing).

Space Complexity: O(1) as we only use a constant number of pointers, regardless of input size.

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

def reverseKGroup(head: ListNode, k: int) -> ListNode:
    # Helper function to count if we have k nodes available
    def hasKNodes(node, k):
        count = 0
        while node and count < k:
            node = node.next
            count += 1
        return count == k
    
    # Helper function to reverse k nodes starting from head
    def reverseK(head, k):
        prev = None
        curr = head
        for _ in range(k):
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node
        return prev, curr  # new head, node after the reversed group
    
    # Use a dummy node to simplify edge cases
    dummy = ListNode(0)
    dummy.next = head
    prev_group_tail = dummy
    
    while head:
        # Check if we have k nodes to reverse
        if not hasKNodes(head, k):
            break
        
        # Remember the start of this group
        group_start = head
        
        # Reverse k nodes
        new_head, next_group_start = reverseK(head, k)
        
        # Connect previous group to the newly reversed group
        prev_group_tail.next = new_head
        
        # group_start is now the tail of the reversed group
        group_start.next = next_group_start
        
        # Move pointers for next iteration
        prev_group_tail = group_start
        head = next_group_start
    
    return dummy.next