Reverse Linked List in Groups of k
Problem
Reverse every consecutive group of k nodes in a singly linked list. Any trailing group of fewer than k nodes stays as is. The cleanest one-pass approach: keep a groupPrev pointer outside the current group; walk k steps to find groupNext (the first node after this group); reverse the group between them, then advance groupPrev to the new tail of the reversed block.
Input
1→2→3→4→5, k=2Output
2→1→4→3→5Two pairs flip; the lone trailing 5 stays.
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.nextfunction 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;
}