25. Reverse Nodes in k-Group

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

Python

Stack and detect length

• Time: O(N+k)
• Space: O(k) # Used on the stack

class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if k < 2:
            # If k == 1, nothing to be changed
            return head

        stack = []
        dummy = ListNode(next=head)

        # gpre stands for group pervious pointer
        gpre, cur = dummy, head

        while cur:
            stack.append(cur)

            if len(stack) % k == 0:
                # Nodes in stack is ready to be reversed
                origin_next = cur.next
                print("Reversing {} -> {} -> {}:".format(
                    gpre.val,
                    [node.val for node in stack],
                    cur.next.val if cur.next else None
                ))

                # Dummy head of the reversing part
                rhead = ListNode()
                rcur = rhead
                while stack:
                    rcur.next = stack.pop()
                    rcur = rcur.next
                    rcur.next = None # To prevent loop, add back after while

                # The rcur now point to the new end of the reversed linked list
                # Maintain the pointers
                rcur.next = origin_next
                gpre.next = rhead.next
                gpre = rcur
                cur = rcur.next
            else:
                cur = cur.next

        return dummy.next