Iterative Solution in Python. Time Complexity O(N) and Space Complexity O(1)


  • 0
    A
    class Solution:
        def reverseKGroup(self, head, k):
            if head is None:
                return head
    
            data = self.reverse(head, k)
    
            new_head = data[0]
            next_head = data[1]
            new_tail = data[2]
    
            while next_head:
                data = self.reverse(next_head, k)
                new_tail.next = data[0]
                next_head = data[1]
                new_tail = data[2]
    
            return new_head
    
        def reverse(self, head, k):
            new_tail = head
            current_node = temp = head
            previous_node = None
            original_tail = None
    
            i = 0
            for _ in range(k):
                if temp:
                    original_tail = temp
                    temp = temp.next
                    i += 1
    
            if i == k:
                for _ in range(k):
                    if current_node is None:
                        break
                    next_node = current_node.next
                    current_node.next = previous_node
                    previous_node = current_node
                    current_node = next_node
    
                return previous_node, current_node, new_tail
            else:
                return head, None, original_tail
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.