LeetCode 25: Reverse Nodes In K Group — Step-by-Step Visual Trace

#leetcode #algorithms #python #datastructures

Hard — Linked List | Recursion | Pointers

The Problem

Given the head of a linked list, reverse the nodes of the list k at a time, returning the modified list. If the number of remaining nodes is not a multiple of k, leave the remaining nodes as they are.

Approach

The algorithm first counts the total nodes to determine if reversal is possible. It then reverses the first k nodes using iterative pointer manipulation, and recursively applies the same process to the remaining list segments.

Time: O(n) · Space: O(n/k)

Code

class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        if not head or k == 1:
            return head

        # Count the number of nodes in the list
        count = 0
        current = head
        while current:
            count += 1
            current = current.next

        if count < k:
            return head

        # Reverse the first k nodes
        prev, current = None, head
        for _ in range(k):
            next_node = current.next
            current.next = prev
            prev = current
            current = next_node

        # Recursively reverse the remaining part of the list
        head.next = self.reverseKGroup(current, k)

        return prev