Language Selection
Choose your preferred programming language
Showing: Python
Problem Statement
Given the head of a linked list, reverse the nodes of the list k at a time, and return the 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.
You may not alter the values in the list’s nodes, only nodes themselves may be changed.
Input/Output Specifications
- Input: Head of a linked list and integer k
- Output: Head of the modified linked list
- Constraints:
- The number of nodes in the list is n
- 1 <= k <= n <= 5000
- 0 <= Node.val <= 1000
Examples
Example 1:
Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]
Example 2:
Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]
Example 3:
Input: head = [1,2,3,4,5], k = 1
Output: [1,2,3,4,5]
Solutions
Approach 1: Iterative (Two Pass)
This approach uses two passes: first to check if there are enough nodes, then to reverse the group.
Algorithm:
- Check if there are at least k nodes remaining
- If yes, reverse the first k nodes
- Recursively process the remaining list
- Connect the reversed group to the result
- Return the new head
Python:
def reverseKGroup(head, k):
"""
Reverse every k consecutive nodes in a linked list
Time: O(n)
Space: O(1)
"""
if not head or k == 1:
return head
# Check if there are at least k nodes
current = head
count = 0
while current and count < k:
current = current.next
count += 1
if count == k:
# Reverse the first k nodes
prev = reverseKGroup(current, k) # Recursively reverse remaining
current = head
while count > 0:
next_temp = current.next
current.next = prev
prev = current
current = next_temp
count -= 1
head = prev
return head
Java:
class Solution {
/**
* Reverse every k consecutive nodes in a linked list
* Time: O(n)
* Space: O(1)
*/
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null || k == 1) {
return head;
}
// Check if there are at least k nodes
ListNode current = head;
int count = 0;
while (current != null && count < k) {
current = current.next;
count++;
}
if (count == k) {
// Reverse the first k nodes
ListNode prev = reverseKGroup(current, k); // Recursively reverse remaining
current = head;
while (count > 0) {
ListNode nextTemp = current.next;
current.next = prev;
prev = current;
current = nextTemp;
count--;
}
head = prev;
}
return head;
}
}
Go:
// reverseKGroup - Reverse every k consecutive nodes in a linked list
// Time: O(n)
// Space: O(1)
func reverseKGroup(head *ListNode, k int) *ListNode {
if head == nil || k == 1 {
return head
}
// Check if there are at least k nodes
current := head
count := 0
for current != nil && count < k {
current = current.Next
count++
}
if count == k {
// Reverse the first k nodes
prev := reverseKGroup(current, k) // Recursively reverse remaining
current = head
for count > 0 {
nextTemp := current.Next
current.Next = prev
prev = current
current = nextTemp
count--
}
head = prev
}
return head
}
JavaScript:
/**
* Reverse every k consecutive nodes in a linked list
* Time: O(n)
* Space: O(1)
*/
function reverseKGroup(head, k) {
if (head === null || k === 1) {
return head;
}
// Check if there are at least k nodes
let current = head;
let count = 0;
while (current !== null && count < k) {
current = current.next;
count++;
}
if (count === k) {
// Reverse the first k nodes
const prev = reverseKGroup(current, k); // Recursively reverse remaining
current = head;
while (count > 0) {
const nextTemp = current.next;
current.next = prev;
prev = current;
current = nextTemp;
count--;
}
head = prev;
}
return head;
}
C#:
public class Solution {
/// <summary>
/// Reverse every k consecutive nodes in a linked list
/// Time: O(n)
/// Space: O(1)
/// </summary>
public ListNode ReverseKGroup(ListNode head, int k) {
if (head == null || k == 1) {
return head;
}
// Check if there are at least k nodes
ListNode current = head;
int count = 0;
while (current != null && count < k) {
current = current.next;
count++;
}
if (count == k) {
// Reverse the first k nodes
ListNode prev = ReverseKGroup(current, k); // Recursively reverse remaining
current = head;
while (count > 0) {
ListNode nextTemp = current.next;
current.next = prev;
prev = current;
current = nextTemp;
count--;
}
head = prev;
}
return head;
}
}
Approach 2: Iterative (Single Pass)
This approach processes the list in a single pass by maintaining pointers to track group boundaries.
Algorithm:
- Use dummy head to simplify edge cases
- Maintain pointers for group start, end, and previous group end
- For each group of k nodes:
- Check if there are enough nodes
- Reverse the group
- Connect to previous group
- Return the head
Python:
def reverseKGroupIterative(head, k):
"""
Reverse every k consecutive nodes using iterative approach
Time: O(n)
Space: O(1)
"""
if not head or k == 1:
return head
dummy = ListNode(0)
dummy.next = head
group_prev = dummy
while True:
# Check if there are at least k nodes
kth = group_prev
for _ in range(k):
kth = kth.next
if not kth:
return dummy.next
# Reverse the group
group_next = kth.next
prev = group_next
current = group_prev.next
while current != group_next:
next_temp = current.next
current.next = prev
prev = current
current = next_temp
# Connect to previous group
temp = group_prev.next
group_prev.next = kth
group_prev = temp
return dummy.next
Java:
class Solution {
/**
* Reverse every k consecutive nodes using iterative approach
* Time: O(n)
* Space: O(1)
*/
public ListNode reverseKGroupIterative(ListNode head, int k) {
if (head == null || k == 1) {
return head;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode groupPrev = dummy;
while (true) {
// Check if there are at least k nodes
ListNode kth = groupPrev;
for (int i = 0; i < k; i++) {
kth = kth.next;
if (kth == null) {
return dummy.next;
}
}
// Reverse the group
ListNode groupNext = kth.next;
ListNode prev = groupNext;
ListNode current = groupPrev.next;
while (current != groupNext) {
ListNode nextTemp = current.next;
current.next = prev;
prev = current;
current = nextTemp;
}
// Connect to previous group
ListNode temp = groupPrev.next;
groupPrev.next = kth;
groupPrev = temp;
}
}
}
Go:
// reverseKGroupIterative - Reverse every k consecutive nodes using iterative approach
// Time: O(n)
// Space: O(1)
func reverseKGroupIterative(head *ListNode, k int) *ListNode {
if head == nil || k == 1 {
return head
}
dummy := &ListNode{Val: 0, Next: head}
groupPrev := dummy
for {
// Check if there are at least k nodes
kth := groupPrev
for i := 0; i < k; i++ {
kth = kth.Next
if kth == nil {
return dummy.Next
}
}
// Reverse the group
groupNext := kth.Next
prev := groupNext
current := groupPrev.Next
for current != groupNext {
nextTemp := current.Next
current.Next = prev
prev = current
current = nextTemp
}
// Connect to previous group
temp := groupPrev.Next
groupPrev.Next = kth
groupPrev = temp
}
}
JavaScript:
/**
* Reverse every k consecutive nodes using iterative approach
* Time: O(n)
* Space: O(1)
*/
function reverseKGroupIterative(head, k) {
if (head === null || k === 1) {
return head;
}
const dummy = new ListNode(0);
dummy.next = head;
let groupPrev = dummy;
while (true) {
// Check if there are at least k nodes
let kth = groupPrev;
for (let i = 0; i < k; i++) {
kth = kth.next;
if (kth === null) {
return dummy.next;
}
}
// Reverse the group
const groupNext = kth.next;
let prev = groupNext;
let current = groupPrev.next;
while (current !== groupNext) {
const nextTemp = current.next;
current.next = prev;
prev = current;
current = nextTemp;
}
// Connect to previous group
const temp = groupPrev.next;
groupPrev.next = kth;
groupPrev = temp;
}
}
C#:
public class Solution {
/// <summary>
/// Reverse every k consecutive nodes using iterative approach
/// Time: O(n)
/// Space: O(1)
/// </summary>
public ListNode ReverseKGroupIterative(ListNode head, int k) {
if (head == null || k == 1) {
return head;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode groupPrev = dummy;
while (true) {
// Check if there are at least k nodes
ListNode kth = groupPrev;
for (int i = 0; i < k; i++) {
kth = kth.next;
if (kth == null) {
return dummy.next;
}
}
// Reverse the group
ListNode groupNext = kth.next;
ListNode prev = groupNext;
ListNode current = groupPrev.next;
while (current != groupNext) {
ListNode nextTemp = current.next;
current.next = prev;
prev = current;
current = nextTemp;
}
// Connect to previous group
ListNode temp = groupPrev.next;
groupPrev.next = kth;
groupPrev = temp;
}
}
}
Key Insights
- Group processing: Process the list in groups of k nodes
- Boundary checking: Always check if there are enough nodes before reversing
- Recursive approach: Elegant but uses O(n/k) recursion stack space
- Iterative approach: More complex but uses O(1) extra space
- Pointer management: Careful handling of group boundaries and connections
Edge Cases
- k equals 1 (no reversal needed)
- k equals list length (reverse entire list)
- k greater than list length (no reversal)
- Empty list
- Single node list
Test Cases
# Test case 1: Normal case
head1 = ListNode(1)
head1.next = ListNode(2)
head1.next.next = ListNode(3)
head1.next.next.next = ListNode(4)
head1.next.next.next.next = ListNode(5)
# reverseKGroup(head1, 2) -> [2,1,4,3,5]
# Test case 2: k = 3
head2 = ListNode(1)
head2.next = ListNode(2)
head2.next.next = ListNode(3)
head2.next.next.next = ListNode(4)
head2.next.next.next.next = ListNode(5)
# reverseKGroup(head2, 3) -> [3,2,1,4,5]
# Test case 3: k = 1
head3 = ListNode(1)
head3.next = ListNode(2)
head3.next.next = ListNode(3)
# reverseKGroup(head3, 1) -> [1,2,3]
# Test case 4: k equals list length
head4 = ListNode(1)
head4.next = ListNode(2)
head4.next.next = ListNode(3)
# reverseKGroup(head4, 3) -> [3,2,1]
Follow-up Questions
- How would you handle very large lists?
- Can you solve this with O(1) space?
- How would you handle lists with cycles?
- What if k is very large?
Common Mistakes
- Not checking if there are enough nodes before reversing
- Incorrect pointer management during group reversal
- Not properly connecting groups together
- Forgetting to handle edge cases like k = 1
- Off-by-one errors in group boundary calculation
- Memory leaks when not properly managing pointers