Reverse Nodes in k-Group

The problem

Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list.

Function: def reverseKGroup(head,k):

Example input (a JSON list of arguments): [[1, 2, 3, 4, 5], 2]
Expected output: [2, 1, 4, 3, 5]

Inputs satisfy the problem statement. Sequences contain at most 200 elements unless a smaller bound is stated. Use JSON values and the supplied function signature.

Hints

1. Check that a complete group of k nodes exists before reversing it.
2. Check the supplied examples, empty/boundary cases and the stated answer policy before optimizing.

Worked answer

Try it yourself first. When you are ready, open the answer below.

def reverseKGroup(head,k):
    dummy=ListNode(0,head);before=dummy
    while True:
        end=before
        for _ in range(k):
            end=end.next
            if not end:return dummy.next
        after=end.next;prev=after;cur=before.next
        while cur is not after:nxt=cur.next;cur.next=prev;prev=cur;cur=nxt
        tail=before.next;before.next=end;before=tail

Why it works

Check that a complete group of k nodes exists before reversing it. Reverse links until the saved successor, reconnect the preceding group, and leave an incomplete final group unchanged.

Complexity: O(n) time / O(1) auxiliary space.

Time: O(n) time · Space: O(1) auxiliary space