🧠
Iterative Approach with Helper Function to Reverse Sublist
💡 This approach modularizes the reversal logic by using a helper function to reverse a sublist between two pointers, improving code readability and maintainability.
Intuition
Split the problem into two parts: a helper to reverse a sublist, and the main function to iterate over the list and reverse groups using the helper.
Algorithm
- Create a dummy node pointing to head.
- Iterate through the list to find groups of k nodes.
- Use a helper function to reverse the nodes between group boundaries.
- Reconnect the reversed group and move to the next group.
💡 Separating reversal logic into a helper clarifies the main loop and reduces complexity in pointer management.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverseBetween(start, end):
prev = None
curr = start
while curr != end:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
return prev
def reverseKGroup(head, k):
dummy = ListNode(0)
dummy.next = head
group_prev = dummy
while True:
kth = group_prev
count = 0
while kth.next and count < k:
kth = kth.next
count += 1
if count < k:
break
group_next = kth.next
# Reverse group
prev = reverseBetween(group_prev.next, group_next)
tmp = group_prev.next
group_prev.next = prev
tmp.next = group_next
group_prev = tmp
return dummy.next
# Driver code
if __name__ == '__main__':
nodes = [ListNode(i) for i in range(1, 6)]
for i in range(4):
nodes[i].next = nodes[i+1]
new_head = reverseKGroup(nodes[0], 2)
curr = new_head
while curr:
print(curr.val, end=' ')
curr = curr.next
Line Notes
def reverseBetween(start, end):Helper reverses nodes from start up to but not including end
while curr != end:Reverse nodes until reaching end boundary
group_next = kth.nextStore next group's start before reversal
tmp.next = group_nextReconnect reversed group to next part of list
class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; this.next = null; }
}
public class Solution {
private ListNode reverseBetween(ListNode start, ListNode end) {
ListNode prev = null;
ListNode curr = start;
while (curr != end) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode groupPrev = dummy;
while (true) {
ListNode kth = groupPrev;
int count = 0;
while (kth.next != null && count < k) {
kth = kth.next;
count++;
}
if (count < k) break;
ListNode groupNext = kth.next;
ListNode prev = reverseBetween(groupPrev.next, groupNext);
ListNode tmp = groupPrev.next;
groupPrev.next = prev;
tmp.next = groupNext;
groupPrev = tmp;
}
return dummy.next;
}
public static void main(String[] args) {
ListNode[] nodes = new ListNode[5];
for (int i = 0; i < 5; i++) nodes[i] = new ListNode(i + 1);
for (int i = 0; i < 4; i++) nodes[i].next = nodes[i + 1];
Solution sol = new Solution();
ListNode newHead = sol.reverseKGroup(nodes[0], 2);
ListNode curr = newHead;
while (curr != null) {
System.out.print(curr.val + " ");
curr = curr.next;
}
}
}
Line Notes
private ListNode reverseBetween(ListNode start, ListNode end)Helper reverses nodes from start up to but not including end
while (curr != end)Reverse nodes until reaching end boundary
ListNode groupNext = kth.next;Save next group's start before reversal
tmp.next = groupNext;Reconnect reversed group to next part
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
class Solution {
public:
ListNode* reverseBetween(ListNode* start, ListNode* end) {
ListNode* prev = nullptr;
ListNode* curr = start;
while (curr != end) {
ListNode* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode dummy(0);
dummy.next = head;
ListNode* groupPrev = &dummy;
while (true) {
ListNode* kth = groupPrev;
int count = 0;
while (kth->next != nullptr && count < k) {
kth = kth->next;
count++;
}
if (count < k) break;
ListNode* groupNext = kth->next;
ListNode* prev = reverseBetween(groupPrev->next, groupNext);
ListNode* tmp = groupPrev->next;
groupPrev->next = prev;
tmp->next = groupNext;
groupPrev = tmp;
}
return dummy.next;
}
};
int main() {
ListNode* nodes[5];
for (int i = 0; i < 5; i++) nodes[i] = new ListNode(i + 1);
for (int i = 0; i < 4; i++) nodes[i]->next = nodes[i + 1];
Solution sol;
ListNode* newHead = sol.reverseKGroup(nodes[0], 2);
ListNode* curr = newHead;
while (curr != nullptr) {
cout << curr->val << " ";
curr = curr->next;
}
cout << endl;
return 0;
}
Line Notes
ListNode* reverseBetween(ListNode* start, ListNode* end)Helper reverses nodes from start up to but not including end
while (curr != end)Reverse nodes until end boundary
ListNode* groupNext = kth->next;Save next group's start before reversal
tmp->next = groupNext;Reconnect reversed group to next part
class ListNode {
constructor(val = 0, next = null) {
this.val = val;
this.next = next;
}
}
function reverseBetween(start, end) {
let prev = null;
let curr = start;
while (curr !== end) {
let next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
function reverseKGroup(head, k) {
const dummy = new ListNode(0, head);
let groupPrev = dummy;
while (true) {
let kth = groupPrev;
let count = 0;
while (kth.next !== null && count < k) {
kth = kth.next;
count++;
}
if (count < k) break;
const groupNext = kth.next;
const prev = reverseBetween(groupPrev.next, groupNext);
const tmp = groupPrev.next;
groupPrev.next = prev;
tmp.next = groupNext;
groupPrev = tmp;
}
return dummy.next;
}
// Driver code
const nodes = [1,2,3,4,5].map(v => new ListNode(v));
for (let i = 0; i < nodes.length - 1; i++) nodes[i].next = nodes[i+1];
const newHead = reverseKGroup(nodes[0], 2);
let curr = newHead;
const output = [];
while (curr !== null) {
output.push(curr.val);
curr = curr.next;
}
console.log(output.join(' '));
Line Notes
function reverseBetween(start, end)Helper reverses nodes from start up to but not including end
while (curr !== end)Reverse nodes until end boundary
const groupNext = kth.next;Save next group's start before reversal
tmp.next = groupNext;Reconnect reversed group to next part
Each node is visited once and reversed in place with no recursion, so time is linear and space is constant.
💡 For n=20 and k=2, the algorithm does about 20 node visits and pointer changes with no extra memory.
Interview Verdict: Accepted and clean modular code
This approach is ideal for writing clean, maintainable code in interviews.