[LeetCode] 25. Reverse Nodes in k-Group

Problem : https://leetcode.com/problems/reverse-nodes-in-k-group/

This problem needs to be solved by 2 nested recursion. The outer recursion locates the groups of k nodes. The inner recursion reverse the located group.

Time Complexity :  O ( N )

Space Complexity : O ( 1 ) 

# 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: ListNode, k: int) -> ListNode:
        if not head:
            return None
        
        # find the first k nodes
        i = 0
        p = head
        
        while i < k and p:
            p = p.next
            i += 1
        
        # return the original list if it has less nodes than k
        if i < k:
            return head
        
        # reverse the first k nodes
        pre = None
        cur = head
               
        while cur != p:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
        
        # append to the rest reversed groups
        head.next = self.reverseKGroup(p, k)
    
        return pre

Updated on 07/18/2021. Update for a simpler recursive solution.