Linked List

Explanation

The function reverses nodes in a linked list in groups of k. Here’s how it works step-by-step:

  1. Helper Function get(p, k):

    • The get function first moves the pointer p forward by k steps to locate the start of the next k-group, storing this position as np.
    • Then, it moves p forward an additional k-1 steps to set ne as the last node of the next k-group.
    • This way, np marks the beginning of the following group, and ne marks its end, helping to identify group boundaries and determine whether the next group is complete.

  2. Main Loop:

    • p starts as the head of the list, and s points to the node next to p.
    • dummy will eventually store the new head of the list after the first k-group is reversed.

  3. Outer Loop - Group Processing:

    • In each iteration, np and ne are updated to mark the beginning and end of the next k-group.
    • If this is the first group (indicated by c == 0), dummy is set to store the new head of the reversed list.

  4. Reversing Each k-Group:

    • The inner while loop reverses the current k-group by reassigning next pointers within that segment.
    • The loop stops once s reaches np, which indicates the start of the next group, signaling the end of the current group's reversal.

  5. Connecting Groups:

    • After reversing a k-group, p moves forward within the reversed segment using a for loop.
    • If ne (the end of the next group) is None, there are fewer than k nodes remaining, so p.next is set to np to link any remaining nodes as they are, and the function returns dummy.
    • Otherwise, p.next is set to ne to link the reversed group to the next full k-group, and p and s are updated to process the following group.

This process continues until all nodes in the list are processed, reversing each k-group in place while preserving the order of any remaining nodes at the end.


class Solution(object):
    def reverseKGroup(self, head, k):
        if k == 1:
            return head
            
        def get(p, k):
            # Move p k steps forward and set np as the start of the next group
            for _ in range(k):
                if p:
                    p = p.next
            np = p
            # Move p k-1 more steps to set ne as the end of the current k-group
            for _ in range(k - 1):
                if p:
                    p = p.next
            ne = p
            return np, ne

        p = head
        s = p.next
        c = 0
        dummy = None

  
        while True:
            # Outer loop: get references for the start and end of the next k-group
            np, ne = get(p, k)
            # Reversal within the current k-group

            while s != np:
                nxt = s.next
                s.next = p
                p = s
                s = nxt


            # Set the dummy head on the first pass

            if c == 0:
                dummy = p

            # Move p forward within the group after reversal
            for _ in range(k - 1):
                p = p.next

            # Check if we have a full k-group to process
            if not ne:
                p.next = np
                return dummy

            else:
                # Connect the end of the current group to the next one
                p.next = ne
                p = np
                s = p.next

            c += 1