Reverse Nodes in k-Group

hard linked list reverse

Problem

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list. k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

Input1→2→3→4→5, k=2

Output2→1→4→3→5

Two pairs flip; the lone trailing 5 stays.

list (comma-separated)

def reverse_k_group(head, k):
    dummy = ListNode(0, head)
    group_prev = dummy
    while True:
        kth = group_prev
        for _ in range(k):
            kth = kth.next
            if kth is None:
                return dummy.next
        group_next = kth.next
        prev, cur = group_next, group_prev.next
        while cur is not group_next:
            tmp = cur.next
            cur.next = prev
            prev = cur
            cur = tmp
        new_tail = group_prev.next
        group_prev.next = kth
        group_prev = new_tail
    return dummy.next

function reverseKGroup(head, k) {
  const dummy = { val: 0, next: head };
  let groupPrev = dummy;
  while (true) {
    let kth = groupPrev;
    for (let i = 0; i < k && kth; i++) kth = kth.next;
    if (!kth) break;
    const groupNext = kth.next;
    let prev = groupNext, cur = groupPrev.next;
    while (cur !== groupNext) {
      const tmp = cur.next;
      cur.next = prev;
      prev = cur;
      cur = tmp;
    }
    const newTail = groupPrev.next;
    groupPrev.next = kth;
    groupPrev = newTail;
  }
  return dummy.next;
}

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0, head), groupPrev = dummy;
        while (true) {
            ListNode kth = groupPrev;
            for (int i = 0; i < k && kth != null; i++) kth = kth.next;
            if (kth == null) break;
            ListNode groupNext = kth.next;
            ListNode prev = groupNext, cur = groupPrev.next;
            while (cur != groupNext) {
                ListNode tmp = cur.next;
                cur.next = prev;
                prev = cur;
                cur = tmp;
            }
            ListNode newTail = groupPrev.next;
            groupPrev.next = kth;
            groupPrev = newTail;
        }
        return dummy.next;
    }
}

ListNode* reverseKGroup(ListNode* head, int k) {
    ListNode dummy(0, head);
    ListNode* groupPrev = &dummy;
    while (true) {
        ListNode* kth = groupPrev;
        for (int i = 0; i < k && kth; ++i) kth = kth->next;
        if (!kth) break;
        ListNode* groupNext = kth->next;
        ListNode* prev = groupNext;
        ListNode* cur = groupPrev->next;
        while (cur != groupNext) {
            ListNode* tmp = cur->next;
            cur->next = prev;
            prev = cur;
            cur = tmp;
        }
        ListNode* newTail = groupPrev->next;
        groupPrev->next = kth;
        groupPrev = newTail;
    }
    return dummy.next;
}

Explanation

The goal is to flip the list in chunks of k nodes at a time, but only when a full chunk of k nodes actually exists. Any leftover nodes at the end that don't fill a whole group are left exactly as they are.

We use a dummy node in front of the head so the very first group has something stable to attach to. A pointer called group_prev always sits just before the group we are about to reverse.

For each round we first walk k steps to find kth, the last node of the group. If we run off the end (it becomes None), the remaining nodes are a partial group and we stop. Otherwise we remember group_next (the node after the group) and do a standard pointer reversal of the k nodes, stopping when we reach group_next.

After reversing, the old first node of the group becomes its new tail, so we reconnect group_prev.next = kth and move group_prev forward to that new_tail to set up for the next group.

Example: 1→2→3→4→5 with k=2. First group 1,2 flips to 2,1; second group 3,4 flips to 4,3; only 5 is left, which isn't a full pair, so it stays. Result: 2→1→4→3→5.

Time: O(n) Space: O(1)