The O(n) Club: Reverse Nodes in K-Group — Now You’re Juggling Pointers and Sanity
⚡ TL;DR
Reverse your singly-linked list in groups of k nodes. If there’s a leftover group that’s smaller than k, pretend you didn’t even see it. Brute force = stack or array (which works, but makes you look like you’re prepping for LinkedIn’s “how NOT to do tech interviews” seminar). Real adults use pointer magic:
🧠 How Devs Usually Mess This Up
Oh, the carnage. Common fails include:
- Reversing every group — including the runt at the end. The last mini-group must stay in witness protection, unreversed.
- Forgetting about links. Skip a pointer update and your list is now two lists (or zero). Hope you weren’t attached.
- Setting
prev = null. Now you’ve cut your beautiful reversed group off from civilization. Next time, use group boundaries for a happier ending.
🔍 What’s Actually Going On
Imagine a delivery line where every batch of k packages flips places for dramatic effect—except the last handful. You let them slide, because nobody likes drama right before home time. The core moves:
- Find the k-th node ahead. No full group? Stop.
- Reverse exactly those k nodes with your spiciest three-pointer maneuver.
- Reconnect the reversed chunk back to main street (the rest of the list).
Bonus tip: a dummy node at the start saves you from annoying edge cases. Like a silent partner who never takes credit or bugs you for status updates.
🛠️ PseudoCode
- Move prev to end of reversed chunk, rinse, repeat
Reconnect the group boundaries.
prevGroup.next = kth;
groupStart.next = groupNext;Do the reversal, using three-pointer gymnastics.
ListNode prev = kth.next;
ListNode curr = prevGroup.next;
while (curr != groupNext)
// swing pointers!Loop to find each k-group:
ListNode kth = getKthNode(prev, k);If none left, escape the matrix.
Set up a dummy node that points at head. Smile and wave at edge cases.
ListNode dummy = new ListNode(0);
dummy.next = head;💻 The Code
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prevGroup = dummy;
while (true) {
ListNode kth = getKthNode(prevGroup, k);
if (kth == null) break;
ListNode groupNext = kth.next;
// Reverse group
ListNode prev = groupNext, curr = prevGroup.next;
while (curr != groupNext) {
ListNode temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
// Plug new head of group
ListNode tmp = prevGroup.next;
prevGroup.next = kth;
prevGroup = tmp;
}
return dummy.next;
}
private ListNode getKthNode(ListNode start, int k) {
while (start != null && k > 0) {
start = start.next;
k--;
}
return start;
}
⚠️ Pitfalls, Traps & Runtime Smacks
- k = 1? You’re done—no reversal needed (but hey, thanks for playing).
- k > length? You’re also done, unless you enjoy empty loops.
- Smaller final group? Just don’t touch it. Seriously.
- Time/Space: Looks like O(n), smells like O(n), is O(n). Space? Constant. Unless you sneak in a stack, and your interviewer cries a single tear.
🧠 Interviewer Brain-Tattoo
“When your pointers go rogue, just remember: even seasoned devs have watched their lists disintegrate like Thanos snapped. Stay sharp, or bring backup coffee.”
