25. Reverse Nodes in k-Group

Recusion

Intuition

This is like a combination of a regular reverse linked question with an extra recursion.

This problem can obviously be solved easily with recursion.

reverseKGroup([1,2,3,4,5], 2) can be divided into 2 parts, reverse [1,2] and reverseKGroup([3,4,5], 2).

Approach

Check if current linked list has at least k nodes, return head if not (this is one of the base cases) Reverse the first k nodes, set a pointer tail on the last node of this reversed sublist Recursively call to reverseKGroup on the rest of the nodes

Complexity

Time complexity: $O(N)$

The list is traversed ~2 times. Once for checking if longer than k, once for actual reversing.

Space complexity:

$O(n/k)$ space to maintain recursion call stack. Other than that, it's $O(1)$ space.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        # Recursive Solution
        # Base Case
        if head is None:
            return head
        # Reverse first k nodes
        k_clone = k
        # check if remaining list is longer than k, without start reversing
        cur = head
        while k_clone > 0 and cur is not None:
            k_clone -= 1
            cur = cur.next
        if k_clone > 0:
            # current linked list is not longer than k
            return head
        tail = head
        prev, cur = head, head.next
        k_clone = k - 1
        # start reversing
        while k_clone > 0 and cur is not None:
            k_clone -= 1
            next = cur.next
            cur.next = prev
            prev = cur
            cur = next

        tail.next = cur
        new_head = prev
        # Recursion
        reversed_sublist = self.reverseKGroup(cur, k)
        tail.next = reversed_sublist
        return new_head