LeetCode 25: Reverse Nodes in k-Group (Segmented Linked-List Rewiring)
LeetCode 25Linked ListPointer RewiringToday we solve LeetCode 25 - Reverse Nodes in k-Group.
Source: https://leetcode.com/problems/reverse-nodes-in-k-group/
English
Problem Summary
Given a singly linked list, reverse nodes in contiguous groups of size k. If the remaining number of nodes is less than k, keep that tail as-is.
Key Insight
Treat each k-group as an isolated segment [groupStart, groupEnd]. First verify the segment has exactly k nodes, then reverse only that segment and reconnect both sides.
Brute Force and Limitations
Brute force copies node values to an array, reverses every k-block in the array, then writes values back. It works but violates the spirit of node-level rewiring and adds extra O(n) space.
Optimal Algorithm Steps (In-Place Segment Reversal)
1) Use a dummy head and pointer groupPrev before current group.
2) Move kth forward k nodes from groupPrev; if not enough nodes, stop.
3) Let groupNext = kth.next. Reverse pointers from groupPrev.next up to kth, using groupNext as boundary.
4) Reconnect: old group head becomes tail and links to groupNext; groupPrev links to new head (kth).
5) Move groupPrev to the new tail and continue.
Complexity Analysis
Time: O(n).
Space: O(1) extra.
Common Pitfalls
- Reversing before confirming k nodes exist.
- Losing groupNext boundary pointer during rewiring.
- Forgetting to update groupPrev to the old head (new tail).
- Mishandling k = 1 or empty list edge cases.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null || k <= 1) return head;
ListNode dummy = new ListNode(0, head);
ListNode groupPrev = dummy;
while (true) {
ListNode kth = getKth(groupPrev, k);
if (kth == null) break;
ListNode groupNext = kth.next;
ListNode prev = groupNext;
ListNode curr = groupPrev.next;
while (curr != groupNext) {
ListNode tmp = curr.next;
curr.next = prev;
prev = curr;
curr = tmp;
}
ListNode newGroupTail = groupPrev.next;
groupPrev.next = kth;
groupPrev = newGroupTail;
}
return dummy.next;
}
private ListNode getKth(ListNode start, int k) {
while (start != null && k > 0) {
start = start.next;
k--;
}
return start;
}
}/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseKGroup(head *ListNode, k int) *ListNode {
if head == nil || k <= 1 {
return head
}
dummy := &ListNode{Next: head}
groupPrev := dummy
for {
kth := getKth(groupPrev, k)
if kth == nil {
break
}
groupNext := kth.Next
prev := groupNext
curr := groupPrev.Next
for curr != groupNext {
tmp := curr.Next
curr.Next = prev
prev = curr
curr = tmp
}
newGroupTail := groupPrev.Next
groupPrev.Next = kth
groupPrev = newGroupTail
}
return dummy.Next
}
func getKth(start *ListNode, k int) *ListNode {
for start != nil && k > 0 {
start = start.Next
k--
}
return start
}/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
if (!head || k <= 1) return head;
ListNode dummy(0, head);
ListNode* groupPrev = &dummy;
while (true) {
ListNode* kth = getKth(groupPrev, k);
if (!kth) break;
ListNode* groupNext = kth->next;
ListNode* prev = groupNext;
ListNode* curr = groupPrev->next;
while (curr != groupNext) {
ListNode* tmp = curr->next;
curr->next = prev;
prev = curr;
curr = tmp;
}
ListNode* newGroupTail = groupPrev->next;
groupPrev->next = kth;
groupPrev = newGroupTail;
}
return dummy.next;
}
private:
ListNode* getKth(ListNode* start, int k) {
while (start && k > 0) {
start = start->next;
--k;
}
return start;
}
};# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
if not head or k <= 1:
return head
dummy = ListNode(0, head)
group_prev = dummy
while True:
kth = self.get_kth(group_prev, k)
if not kth:
break
group_next = kth.next
prev = group_next
curr = group_prev.next
while curr != group_next:
tmp = curr.next
curr.next = prev
prev = curr
curr = tmp
new_group_tail = group_prev.next
group_prev.next = kth
group_prev = new_group_tail
return dummy.next
def get_kth(self, start: ListNode, k: int) -> Optional[ListNode]:
while start and k > 0:
start = start.next
k -= 1
return start/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
var reverseKGroup = function(head, k) {
if (!head || k <= 1) return head;
const dummy = new ListNode(0, head);
let groupPrev = dummy;
while (true) {
const kth = getKth(groupPrev, k);
if (!kth) break;
const groupNext = kth.next;
let prev = groupNext;
let curr = groupPrev.next;
while (curr !== groupNext) {
const tmp = curr.next;
curr.next = prev;
prev = curr;
curr = tmp;
}
const newGroupTail = groupPrev.next;
groupPrev.next = kth;
groupPrev = newGroupTail;
}
return dummy.next;
};
function getKth(start, k) {
while (start && k > 0) {
start = start.next;
k--;
}
return start;
}中文
题目概述
给定单链表，每 k 个节点作为一组进行翻转；如果最后剩余节点数小于 k，则保持原顺序不变。
核心思路
把链表分成一个个长度为 k 的连续片段。先检查片段是否足够 k 个节点，再只在该片段内做原地反转，最后把前后链路重新接回去。
暴力解法与不足
暴力做法是把节点值拷贝到数组，按 k 分组反转后再写回链表。虽然可行，但用了额外 O(n) 空间，也偏离了题目强调的节点级指针操作。
最优算法步骤（分段原地反转）
1）使用哑节点 dummy，groupPrev 指向当前分组前一个节点。
2）从 groupPrev 向后走 k 步找到 kth，若不足 k 个直接结束。
3）记录 groupNext = kth.next，在 [groupPrev.next, kth] 区间内反转指针。
4）重连：旧组头变组尾并接到 groupNext，groupPrev.next 接到新组头。
5）将 groupPrev 移到新组尾，继续下一组。
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(1) 额外空间。
常见陷阱
- 没先判断节点数量是否达到 k 就开始反转。
- 反转过程中丢失 groupNext 边界指针。
- 忘记把 groupPrev 更新为旧组头（反转后组尾）。
- 没处理 k = 1 或空链表。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null || k <= 1) return head;
ListNode dummy = new ListNode(0, head);
ListNode groupPrev = dummy;
while (true) {
ListNode kth = getKth(groupPrev, k);
if (kth == null) break;
ListNode groupNext = kth.next;
ListNode prev = groupNext;
ListNode curr = groupPrev.next;
while (curr != groupNext) {
ListNode tmp = curr.next;
curr.next = prev;
prev = curr;
curr = tmp;
}
ListNode newGroupTail = groupPrev.next;
groupPrev.next = kth;
groupPrev = newGroupTail;
}
return dummy.next;
}
private ListNode getKth(ListNode start, int k) {
while (start != null && k > 0) {
start = start.next;
k--;
}
return start;
}
}/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseKGroup(head *ListNode, k int) *ListNode {
if head == nil || k <= 1 {
return head
}
dummy := &ListNode{Next: head}
groupPrev := dummy
for {
kth := getKth(groupPrev, k)
if kth == nil {
break
}
groupNext := kth.Next
prev := groupNext
curr := groupPrev.Next
for curr != groupNext {
tmp := curr.Next
curr.Next = prev
prev = curr
curr = tmp
}
newGroupTail := groupPrev.Next
groupPrev.Next = kth
groupPrev = newGroupTail
}
return dummy.Next
}
func getKth(start *ListNode, k int) *ListNode {
for start != nil && k > 0 {
start = start.Next
k--
}
return start
}/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
if (!head || k <= 1) return head;
ListNode dummy(0, head);
ListNode* groupPrev = &dummy;
while (true) {
ListNode* kth = getKth(groupPrev, k);
if (!kth) break;
ListNode* groupNext = kth->next;
ListNode* prev = groupNext;
ListNode* curr = groupPrev->next;
while (curr != groupNext) {
ListNode* tmp = curr->next;
curr->next = prev;
prev = curr;
curr = tmp;
}
ListNode* newGroupTail = groupPrev->next;
groupPrev->next = kth;
groupPrev = newGroupTail;
}
return dummy.next;
}
private:
ListNode* getKth(ListNode* start, int k) {
while (start && k > 0) {
start = start->next;
--k;
}
return start;
}
};# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
if not head or k <= 1:
return head
dummy = ListNode(0, head)
group_prev = dummy
while True:
kth = self.get_kth(group_prev, k)
if not kth:
break
group_next = kth.next
prev = group_next
curr = group_prev.next
while curr != group_next:
tmp = curr.next
curr.next = prev
prev = curr
curr = tmp
new_group_tail = group_prev.next
group_prev.next = kth
group_prev = new_group_tail
return dummy.next
def get_kth(self, start: ListNode, k: int) -> Optional[ListNode]:
while start and k > 0:
start = start.next
k -= 1
return start/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
var reverseKGroup = function(head, k) {
if (!head || k <= 1) return head;
const dummy = new ListNode(0, head);
let groupPrev = dummy;
while (true) {
const kth = getKth(groupPrev, k);
if (!kth) break;
const groupNext = kth.next;
let prev = groupNext;
let curr = groupPrev.next;
while (curr !== groupNext) {
const tmp = curr.next;
curr.next = prev;
prev = curr;
curr = tmp;
}
const newGroupTail = groupPrev.next;
groupPrev.next = kth;
groupPrev = newGroupTail;
}
return dummy.next;
};
function getKth(start, k) {
while (start && k > 0) {
start = start.next;
k--;
}
return start;
}
Comments