Reverse Nodes in k-Group solution and explanation
Google
Cisco
9 more videos on this problem
L21. Reverse Nodes in K Group Size of LinkedListtake U forward · 24:31 · 286K views
Reverse Nodes in K-Group - Linked List - Leetcode 25NeetCode · 12:20 · 177K views
Reverse Nodes in K-Group | Linked ListShradha Khapra · 20:39 · 75K views
Reverse Nodes in k-Group O(1) | Live Coding with Explanation | Leetcode - 25Algorithms Made Easy · 15:25 · 14K views
[Java] Leetcode 25. Reverse Nodes in k-Group [LinkedList Reversal #3]Eric Programming · 11:37 · 5K views
REVERSE NODES IN K GROUP | LEETCODE 25 | PYTHON SOLUTIONCracking FAANG · 18:01 · 2K views
Reverse Nodes in k-Group Python Solution - LeetCode #25Professor Oakes · 7:48 · 959 views
Reverse Nodes In K-Group | LeetCode 25 (Hard)Destination FAANG · 17:23 · 734 views
51. Reverse Nodes in k-Group || Linked List || Top 150+ DSA Leetcode Coding JAVAItsruntym · 16:03 · 325 views
Reverse Nodes in k-Group - Leetcode 25 - Explanation & Dry RunArindam Keswani · 11:08 · 268 views
The problem
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.
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]
Constraints:
- The number of nodes in the list is
n. 1 <= k <= n <= 50000 <= Node.val <= 1000
Follow-up: Can you solve the problem in O(1) extra memory space?
Approach overview
Problem Overview: You are given the head of a singly linked list and an integer k. Reverse the nodes of the list k at a time. If the number of remaining nodes is less than k, leave them as they are. Node values cannot be modified; only pointers can be changed.
This problem tests pointer manipulation on a linked list. The key challenge is reversing exactly k nodes at a time while reconnecting the reversed segments back into the original list.
Approach 1: Iterative Group Reversing (O(n) time, O(1) space)
Traverse the list and process it in fixed-size groups of k. First, check whether k nodes exist ahead using a pointer scan. If fewer than k nodes remain, stop and keep them unchanged. When a valid group is found, reverse the k nodes using the standard in-place linked list reversal technique: iterate through the group and redirect next pointers one by one.
After reversing a group, reconnect three parts: the previous group's tail, the new head of the reversed group, and the next group's starting node. A dummy node before the head simplifies edge cases where the first group gets reversed. This approach touches each node a constant number of times, giving O(n) time complexity and O(1) extra space. This is the most common production-style implementation.
Approach 2: Recursive Group Reversal (O(n) time, O(n/k) recursion stack)
The recursive approach treats the list as repeating blocks of size k. First verify that k nodes exist. If they do, reverse the first k nodes using an iterative reversal loop. After reversing the block, recursively process the remainder of the list starting from the (k+1)th node.
The original head of the block becomes the tail after reversal. Connect this node to the result returned by the recursive call. Each recursive frame processes exactly one block of size k, so the total work remains O(n). The recursion stack depth is about n/k, which gives O(n/k) auxiliary space.
This approach reads naturally because each call solves one block and delegates the rest. It is a good demonstration of recursion applied to pointer structures, though it uses extra stack space compared to the iterative version.
Recommended for interviews: The iterative group-reversal approach is typically expected. It demonstrates strong control over pointer manipulation, constant-space optimization, and careful handling of boundary conditions. Showing the recursive idea first can communicate conceptual clarity, but the iterative solution proves you can implement an optimal O(n) and O(1) solution.
Approach 1: Iterative Group Reversing
Use an iterative approach to reverse each group of k nodes separately. This approach leverages an auxiliary dummy node and previous and current pointers to manage the connections at each step. We traverse the list, checking for complete sets of k nodes to reverse them. If a group of nodes has less than k nodes, leave them as they are.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
if not head or k == 1:
return head
dummy = ListNode(0)
dummy.next = head
prev, current = dummy, head
length = 0
while current:
length += 1
current = current.next
while length >= k:
current = prev.next
next = current.next
for i in range(1, k):
current.next = next.next
next.next = prev.next
prev.next = next
next = current.next
prev = current
length -= k
return dummy.nextclass ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null || k == 1) return head;
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy, current = head;
int len = 0;
while (current != null) {
len++;
current = current.next;
}
current = dummy.next;
while (len >= k) {
current = prev.next;
ListNode next = current.next;
for (int i = 1; i < k; ++i) {
current.next = next.next;
next.next = prev.next;
prev.next = next;
next = current.next;
}
prev = current;
len -= k;
}
return dummy.next;
}
}#include <iostream>
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
if (!head || k == 1) return head;
ListNode dummy(0);
dummy.next = head;
ListNode* prev = &dummy;
ListNode* current = head;
int len = 0;
while (current) {
len++;
current = current->next;
}
while (len >= k) {
current = prev->next;
ListNode* next = current->next;
for (int i = 1; i < k; ++i) {
current->next = next->next;
next->next = prev->next;
prev->next = next;
next = current->next;
}
prev = current;
len -= k;
}
return dummy.next;
}
};function ListNode(val, next) {
this.val = val || 0;
this.next = next || null;
}
var reverseKGroup = function(head, k) {
if (!head || k === 1) return head;
const dummy = new ListNode(0);
dummy.next = head;
let prev = dummy, current = head;
let len = 0;
while (current) {
len++;
current = current.next;
}
while (len >= k) {
current = prev.next;
let next = current.next;
for (let i = 1; i < k; ++i) {
current.next = next.next;
next.next = prev.next;
prev.next = next;
next = current.next;
}
prev = current;
len -= k;
}
return dummy.next;
};#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* reverseKGroup(struct ListNode* head, int k) {
if (!head || k == 1) return head;
struct ListNode dummy = {0, head};
struct ListNode *prev = &dummy, *current = head;
int len = 0;
while (current) {
len++;
current = current->next;
}
while (len >= k) {
current = prev->next;
struct ListNode *next = current->next;
for (int i = 1; i < k; i++) {
current->next = next->next;
next->next = prev->next;
prev->next = next;
next = current->next;
}
prev = current;
len -= k;
}
return dummy.next;
}public class ListNode {
public int val;
public ListNode next;
public ListNode(int x) { val = x; }
}
public class Solution {
public ListNode ReverseKGroup(ListNode head, int k) {
if (head == null || k == 1) return head;
ListNode dummy = new ListNode(0) { next = head };
ListNode prev = dummy, current = head;
int len = 0;
while (current != null)
{
len++;
current = current.next;
}
while (len >= k) {
current = prev.next;
ListNode next = current.next;
for (int i = 1; i < k; ++i) {
current.next = next.next;
next.next = prev.next;
prev.next = next;
next = current.next;
}
prev = current;
len -= k;
}
return dummy.next;
}
}The solution constructs a dummy node linked to the head, simplifying edge operations. Counting list length allows determination of how many full k-reversals are possible. Nodes in these groups are then reversed using iterative swaps of pointers.
Time Complexity: O(n), due to single traversal of list nodes.
Space Complexity: O(1), since pointer manipulations require constant space.
Approach 2: Recursive Group Reversal
Recurse through the linked list, reversing k nodes at a time. If a full group of k nodes is found, reverse and connect through recursive calls. Terminate when fewer than k nodes are left. This approach inherently uses the call stack for management of reverse sequences.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
count = 0
current = head
while current and count < k:
current = current.next
count += 1
if count == k:
current = self.reverseKGroup(current, k)
while count > 0:
tmp = head.next
head.next = current
current = head
head = tmp
count -= 1
head = current
return headclass ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null) return null;
ListNode current = head;
int count = 0;
while (current != null && count < k) {
current = current.next;
count++;
}
if (count == k) {
current = reverseKGroup(current, k);
while (count-- > 0) {
ListNode temp = head.next;
head.next = current;
current = head;
head = temp;
}
head = current;
}
return head;
}
}#include <iostream>
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
if (!head) return nullptr;
ListNode* current = head;
int count = 0;
while (current && count < k) {
current = current->next;
count++;
}
if (count == k) {
current = reverseKGroup(current, k);
while (count--) {
ListNode* temp = head->next;
head->next = current;
current = head;
head = temp;
}
head = current;
}
return head;
}
};function ListNode(val, next) {
this.val = val || 0;
this.next = next || null;
}
var reverseKGroup = function(head, k) {
let current = head;
let count = 0;
while (current !== null && count < k) {
current = current.next;
count++;
}
if (count === k) {
current = reverseKGroup(current, k);
while (count-- > 0) {
let tmp = head.next;
head.next = current;
current = head;
head = tmp;
}
head = current;
}
return head;
};#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* reverseLinkedList(struct ListNode* head, int k) {
struct ListNode *prev = NULL, *next = NULL, *current = head;
int count = 0;
while (current != NULL && count < k) {
next = current->next;
current->next = prev;
prev = current;
current = next;
count++;
}
return prev;
}
struct ListNode* reverseKGroup(struct ListNode* head, int k) {
struct ListNode *current = head;
int count = 0;
while (current != NULL && count < k) {
current = current->next;
count++;
}
if (count == k) {
struct ListNode *reversedHead = reverseLinkedList(head, k);
head->next = reverseKGroup(current, k);
return reversedHead;
}
return head;
}public class ListNode {
public int val;
public ListNode next;
public ListNode(int x) { val = x; }
}
public class Solution {
public ListNode ReverseKGroup(ListNode head, int k) {
if (head == null)
return null;
ListNode current = head;
int count = 0;
while (current != null && count < k) {
current = current.next;
count++;
}
if (count == k) {
current = ReverseKGroup(current, k);
while (count-- > 0) {
ListNode tmp = head.next;
head.next = current;
current = head;
head = tmp;
}
head = current;
}
return head;
}
}The function probes node groups, inspecting k node availability. Featuring recursive return principles, node alignment reverses within recursive function sweeps which link completed segments reverting at recursion levels until resolution.
Time Complexity: O(n); within linear complexity, list travel entails single-time node enfranchisement per step.
Space Complexity: O(n/k), involving recursion stack allocating depth aligned to completely reversed portions.
Approach 3: Simulation
We can simulate the entire reversal process according to the problem description.
First, we define a helper function reverse to reverse a linked list. Then, we define a dummy head node dummy and set its next pointer to head.
Next, we traverse the linked list, processing k nodes at a time. If the remaining nodes are fewer than k, we do not perform the reversal. Otherwise, we extract k nodes and call the reverse function to reverse these k nodes. Then, we connect the reversed linked list back to the original linked list. We continue to process the next k nodes until the entire linked list is traversed.
The time complexity is O(n), where n is the length of the linked list. The space complexity is O(1).
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function reverseKGroup(head: ListNode | null, k: number): ListNode | null {
const dummy = new ListNode(0, head);
let pre = dummy;
while (pre !== null) {
let cur: ListNode | null = pre;
for (let i = 0; i < k; i++) {
cur = cur?.next || null;
if (cur === null) {
return dummy.next;
}
}
const node = pre.next;
const nxt = cur?.next || null;
cur!.next = null;
pre.next = reverse(node);
node!.next = nxt;
pre = node!;
}
return dummy.next;
}
function reverse(head: ListNode | null): ListNode | null {
let dummy: ListNode | null = null;
let cur = head;
while (cur !== null) {
const nxt = cur.next;
cur.next = dummy;
dummy = cur;
cur = nxt;
}
return dummy;
}/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseKGroup(head *ListNode, k int) *ListNode {
dummy := &ListNode{Next: head}
pre := dummy
for pre != nil {
cur := pre
for i := 0; i < k; i++ {
cur = cur.Next
if cur == nil {
return dummy.Next
}
}
node := pre.Next
nxt := cur.Next
cur.Next = nil
pre.Next = reverse(node)
node.Next = nxt
pre = node
}
return dummy.Next
}
func reverse(head *ListNode) *ListNode {
var dummy *ListNode
cur := head
for cur != nil {
nxt := cur.Next
cur.Next = dummy
dummy = cur
cur = nxt
}
return dummy
}// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
// pub val: i32,
// pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
// #[inline]
// fn new(val: i32) -> Self {
// ListNode {
// next: None,
// val
// }
// }
// }
impl Solution {
pub fn reverse_k_group(head: Option<Box<ListNode>>, k: i32) -> Option<Box<ListNode>> {
fn reverse(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
let mut head = head;
let mut pre = None;
while let Some(mut node) = head {
head = node.next.take();
node.next = pre.take();
pre = Some(node);
}
pre
}
let mut dummy = Some(Box::new(ListNode::new(0)));
let mut pre = &mut dummy;
let mut cur = head;
while cur.is_some() {
let mut q = &mut cur;
for _ in 0..k - 1 {
if q.is_none() {
break;
}
q = &mut q.as_mut().unwrap().next;
}
if q.is_none() {
pre.as_mut().unwrap().next = cur;
return dummy.unwrap().next;
}
let b = q.as_mut().unwrap().next.take();
pre.as_mut().unwrap().next = reverse(cur);
while pre.is_some() && pre.as_mut().unwrap().next.is_some() {
pre = &mut pre.as_mut().unwrap().next;
}
cur = b;
}
dummy.unwrap().next
}
}/**
* Definition for a singly-linked list.
* class ListNode {
* public $val = 0;
* public $next = null;
* function __construct($val = 0, $next = null) {
* $this->val = $val;
* $this->next = $next;
* }
* }
*/
class Solution {
/**
* @param ListNode $head
* @param Integer $k
* @return ListNode
*/
function reverseKGroup($head, $k) {
$dummy = new ListNode(0);
$dummy->next = $head;
$pre = $dummy;
while ($pre !== null) {
$cur = $pre;
for ($i = 0; $i < $k; $i++) {
if ($cur->next === null) {
return $dummy->next;
}
$cur = $cur->next;
}
$node = $pre->next;
$nxt = $cur->next;
$cur->next = null;
$pre->next = $this->reverse($node);
$node->next = $nxt;
$pre = $node;
}
return $dummy->next;
}
/**
* Helper function to reverse a linked list.
* @param ListNode $head
* @return ListNode
*/
function reverse($head) {
$prev = null;
$cur = $head;
while ($cur !== null) {
$nxt = $cur->next;
$cur->next = $prev;
$prev = $cur;
$cur = $nxt;
}
return $prev;
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative Group Reversing | Time Complexity: O(n), due to single traversal of list nodes. |
| Recursive Group Reversal | Time Complexity: O(n); within linear complexity, list travel entails single-time node enfranchisement per step. |
| Simulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Group Reversing | O(n) | O(1) | Best general solution. Constant extra space and commonly expected in interviews. |
| Recursive Group Reversal | O(n) | O(n/k) | Useful when recursion makes the logic easier to express or when demonstrating recursive linked list manipulation. |
Frequently asked questions
Is Reverse Nodes in k-Group easy or hard?
Reverse Nodes in k-Group is categorized as a hard problem because it requires careful pointer manipulation, handling partial groups, and maintaining correct connections between segments. The algorithm itself is linear, but implementing it without mistakes can be challenging.
Reverse Nodes in k-Group Python/Java solution
Both Python and Java solutions follow the same algorithm: iterate through the list, confirm k nodes exist, reverse the block using pointer updates, and reconnect it to the rest of the list. The logic remains identical across languages, with differences only in syntax and class definitions for the linked list node.
How to solve Reverse Nodes in k-Group in O(n)?
Process the linked list in groups of size k. For each group, first verify that k nodes exist, then reverse those k nodes using in-place pointer reversal. After reversing, connect the previous group's tail to the new head of the reversed block and continue scanning the list. This ensures each node is processed only a few times, giving O(n) time complexity.
What is the best approach for Reverse Nodes in k-Group?
The iterative group reversal approach is considered the best solution. It scans the list, reverses nodes in blocks of k using pointer manipulation, and reconnects the segments. This method runs in O(n) time and uses O(1) extra space, which is typically the optimal solution expected in interviews.
Is Reverse Nodes in k-Group asked at Google/Amazon/Meta?
Reverse Nodes in k-Group is a well-known hard linked list problem frequently discussed in interviews at large tech companies such as Amazon, Google, and Meta. Interviewers use it to evaluate pointer manipulation, edge case handling, and understanding of linked list operations.
What data structure is used in Reverse Nodes in k-Group?
The problem operates on a singly linked list. The solution relies on pointer manipulation to reverse segments of nodes and reconnect them correctly. No additional data structures are required in the optimal implementation.
What is the time complexity of Reverse Nodes in k-Group?
The optimal time complexity is O(n), where n is the number of nodes in the linked list. Each node is visited a constant number of times during group validation and reversal. The iterative approach achieves this with O(1) extra space, while the recursive version uses O(n/k) stack space.