Problem
Given the head of a linked list, reverse the nodes k at a time. Nodes left over (less than k) stay as-is.
Example
Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]Solution
Recursive: count k nodes ahead. If enough exist, reverse that group and recurse on the rest.
def reverse_k_group(head, k):
curr = head
count = 0
while curr and count < k:
curr = curr.next
count += 1
if count < k: return head
prev = reverse_k_group(curr, k)
while count > 0:
next_node = head.next
head.next = prev
prev = head
head = next_node
count -= 1
return prevfunction reverseKGroup(head, k) {
let curr = head, count = 0;
while (curr && count < k) { curr = curr.next; count++; }
if (count < k) return head;
let prev = reverseKGroup(curr, k);
while (count > 0) {
const next = head.next;
head.next = prev;
prev = head;
head = next;
count--;
}
return prev;
}ListNode* reverseKGroup(ListNode* head, int k) {
ListNode* curr = head;
int count = 0;
while (curr && count < k) { curr = curr->next; count++; }
if (count < k) return head;
ListNode* prev = reverseKGroup(curr, k);
while (count-- > 0) {
ListNode* next = head->next;
head->next = prev;
prev = head;
head = next;
}
return prev;
}public ListNode reverseKGroup(ListNode head, int k) {
ListNode curr = head;
int count = 0;
while (curr != null && count < k) { curr = curr.next; count++; }
if (count < k) return head;
ListNode prev = reverseKGroup(curr, k);
while (count-- > 0) {
ListNode next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}Complexity
- Time: O(n)
- Space: O(n/k) recursion
Explanation
Recursive structure: reverse first k nodes, recursively handle the rest, link them. Counting first ensures we don’t reverse a partial group.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?