Leetcode 25. Reverse Nodes in k-Group

Problem

Leetcode 25 - Reverse Nodes in k-Group

Example:

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

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

Approach

First we get a helper function to get Kth node

Then we reverse the nodes from groupPrev to kNode

• groupPrev: first it’s dummy node, then k-1th node
• kNode: to indicate the k’th node if this is None, we should return
• groupNext: k+1’th node
• prev: k+1’th node, use this for reversing the subgroup of nodes
• curr: current node, use this for reversing the subgroup of nodes

Once reversing of subgroup is done, we must connect the groupPrev to subgroup’s new head (reversed head)

• temp = groupPrev.next (should be the new tail)
• groupPrev.next = kNode (should be the new head)
• groupPrev = temp

Visualization of the Approach:

head = [1,2,3,4,5], k = 2
dummy -> 1 -> 2 -> 3 -> 4 -> 5
groupPrev = dummy
kNode = 2
groupNext = 3
prev, curr = 3, 1

dummy -> 2 -> 1 -> 3 -> 4 -> 5
groupPrev = 1
kNode = 4
groupNext = 5
prev, curr = 5, 3

dummy -> 2 -> 1 -> 4 -> 3 -> 5
groupPrev = 3
kNode = None
thus return dummy.next

Here is the Python code for the solution:

class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        groupPrev = dummy

        while True:
            kNode = self.getKth(groupPrev, k)
            if not kNode:
                break

            groupNext = kNode.next
            prev, curr = kNode.next, groupPrev.next

            while curr != groupNext:
                temp = curr.next
                curr.next = prev
                prev = curr
                curr = temp

            temp = groupPrev.next
            groupPrev.next = kNode
            groupPrev = temp
            
        return dummy.next

    def getKth(self, curr, k):
        while curr and k > 0:
            curr = curr.next
            k -= 1

        return curr    

Time Complexity and Space Complexity

Time Complexity: $O(n)$

Space Complexity: $O(1)$