Python 0025.py
class Solution:
def reverse(self, head, depth):
if depth == 1:
if head:
head.next = None
return head
if not head or not head.next:
return head
result = self.reverse(head.next, depth - 1)
head.next.next = head
head.next = None
return result
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
if k <= 1:
return head
# not optimal ... split into chunks and reverse them
parts = []
current = head
while current:
next = current
size = 0
while next and size < k:
next = next.next
size += 1
chunk = current
if size == k:
chunk = self.reverse(current, k)
parts.append(chunk)
current = next
# merge all chunks
tail = None
for p in reversed(parts):
last = p
while last.next:
last = last.next
last.next = tail
tail = p
return tail
Difficulty
and has an acceptance rate of about 67% (2+ million submissions).
Typical patterns to solve this problem:
- Linked List
- Recursion
AI Disclaimer
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.
See this dedicated page for more details.
Code Walkthrough
Overview
The implementation provides a solution for reversing nodes of a singly-linked list in groups of size k. The algorithm proceeds in three conceptual phases: a depth-limited recursive reversal, a traversal that partitions the list into fixed-size chunks, and a final stitching step that reassembles the processed chunks in the original order. The code is organized into two methods: reverse, which performs a recursive reversal of exactly depth nodes, and reverseKGroup, which orchestrates the grouping, conditional reversal, and concatenation.
Core Recursive Reverse
The reverse method is a classic depth-limited recursion that inverts the direction of links for a contiguous segment of the list. When the requested depth equals 1, the method isolates the single node by setting its next pointer to None and returns it as the new head of the segment. For deeper recursion, the method first obtains the reversed tail of the sub-list by calling itself with head.next and a decremented depth. After the recursive call returns, the original head is attached to the end of the reversed sub-list by assigning head.next.next = head and then breaking the original forward link with head.next = None. The resulting head of the reversed segment is propagated back up the call stack.
def reverse(self, head, depth):
if depth == 1:
if head:
head.next = None
return head
if not head or not head.next:
return head
result = self.reverse(head.next, depth - 1)
head.next.next = head
head.next = None
return result
Chunk Partitioning
reverseKGroup begins by handling the trivial case where k is less than or equal to 1, returning the original list unchanged. The main loop walks through the list, extracting consecutive groups of up to k nodes. For each iteration, a nested loop advances a temporary pointer next while counting nodes until either k nodes have been seen or the list ends. The variable size records how many nodes were actually traversed. The pointer current marks the start of the current group, and after the inner loop finishes, next points to the node immediately following the group.
parts = []
current = head
while current:
next = current
size = 0
while next and size < k:
next = next.next
size += 1
Chunk Reversal Decision
If the counted size equals k, the group constitutes a full chunk eligible for reversal. The method invokes self.reverse(current, k) to obtain the reversed segment, assigning the result back to chunk. When the group is smaller than k (i.e., at the tail of the list), the original ordering is preserved by leaving chunk as current. Each processed chunk-reversed or untouched-is appended to the parts list for later merging.
chunk = current
if size == k:
chunk = self.reverse(current, k)
parts.append(chunk)
current = next
Merging Chunks
After all groups have been collected, the algorithm reassembles them into a single list. It iterates over the parts collection in reverse order, ensuring that the original relative order of chunks is maintained. For each chunk p, the code walks to its terminal node last by following next pointers until last.next is None. The terminal node’s next reference is then linked to the previously built tail, and tail is updated to point to the current chunk. When the loop finishes, tail references the head of the fully reconstructed list.
tail = None
for p in reversed(parts):
last = p
while last.next:
last = last.next
last.next = tail
tail = p
return tail
Edge Cases Handled
The recursive reverse method explicitly checks for a depth of 1, guaranteeing that a solitary node is correctly terminated without dangling references. It also guards against null inputs and premature list termination by returning the head unchanged when head or head.next is missing, which prevents attempts to access attributes of a None object.
In the grouping phase, the inner loop’s condition while next and size < k naturally stops at the end of the list, allowing the algorithm to detect incomplete final groups. The subsequent if size == k test ensures that only full groups undergo reversal, leaving a trailing segment of length less than k intact. This behavior aligns with the typical definition of the problem where partial groups are not reversed.
The merging step accommodates chunks that may consist of a single node (including the case where the original list is empty) by correctly handling the while last.next traversal, which terminates immediately when last.next is None. The initialization of tail to None guarantees that the final concatenation produces a proper list termination.
Performance Optimizations
The recursive reversal operates in place, reusing the existing node objects and only adjusting pointer fields. By terminating the recursion exactly at the required depth, the method avoids traversing beyond the intended segment, which reduces unnecessary work for each group.
During chunk partitioning, the algorithm advances a pointer only once per node, achieving a single pass over the input list to identify group boundaries. The decision to reverse a group is made immediately after counting, eliminating the need for a separate pass to locate the end of the group.
The merging phase leverages a reverse iteration over the stored chunks, which allows each chunk’s tail to be found by a straightforward linear walk from its head. Although this introduces a secondary traversal within each chunk, the overall structure avoids repeated scanning of the entire list. By linking chunks from the end toward the front, the code builds the final list without requiring additional auxiliary data structures beyond the parts list, keeping memory usage modest.
Collectively, the design balances recursive depth-limited reversal with iterative grouping and stitching, delivering an in-place transformation that respects group size constraints while maintaining linear traversal characteristics.
ELI5 - Simplified Explanation
Imagine a long line of toy trains hooked together in a row. Sometimes, the goal is to take a small group of these trains and turn them so they face the opposite way, like reversing a little train track layout.
The code works by first looking at the whole line and breaking it into smaller groups, each with the same number of trains. If a group is the right size, the computer picks up those specific trains and flips them around so the last one becomes the first one. It does this by carefully rearranging the little hook connectors that keep the trains attached to each other.
After all the groups are flipped, the code looks at the newly turned groups. It moves through the list starting from the end and attaches the tail of one group to the front of the next one until everything is reconnected in the right order. It repeats this process until every wagon and engine is linked up again just the way it should be.
Code Quality
Complexity Analysis
Other Solutions
Obviously, I did that after I solved the problem myself.
In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.
And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.
(click on a column header to sort the table)
| author | ||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| author | solutions | |||||||||||||
| www | AlgoMonster | C++ | Python | Java | TS | |||||||||
| WalkCCC | C++ | Python | Java | |||||||||||
| leetcode.ca | C++ | Python | Rust | C# | Java | Go | PHP | TS | ||||||
| LeetcodeHelp | C++ | Python | Java | |||||||||||
| MemoryLimitExceeded | C++ | Python | ||||||||||||
| Progiez | C++ | Python | Java | |||||||||||
| github | AdelDaniel | Dart | ||||||||||||
| aylei | Rust | |||||||||||||
| begeekmyfriend | C | |||||||||||||
| BigEggStudy | C# | |||||||||||||
| black-shadows | C++ | |||||||||||||
| bujosa | Rust | |||||||||||||
| charles-wangkai | Java | |||||||||||||
| chenyanzhe | C++ | |||||||||||||
| everthis | JS | |||||||||||||
| fartem | Ruby | |||||||||||||
| fengvyi | C++ | |||||||||||||
| gaosq0604 | Python | |||||||||||||
| Garvit244 | Python | |||||||||||||
| halfrost | Go | |||||||||||||
| haoel | C++ | |||||||||||||
| JoshCrozier | JS | |||||||||||||
| keineahnung2345 | C++ | |||||||||||||
| lennylxx | C | |||||||||||||
| linouk23 | C++ | |||||||||||||
| lkwq007 | Python | |||||||||||||
| luangong | C++ | |||||||||||||
| MacJim | C++ | |||||||||||||
| qiyuangong | Python | |||||||||||||
| ruoru | Rust | |||||||||||||
| Shamik07 | Dart | |||||||||||||
| shreymehul | C# | |||||||||||||
| sonugiri1043 | C++ | |||||||||||||
| suxrobGM | C# | |||||||||||||
| trung-hn | Python | |||||||||||||
| varunu28 | Java | |||||||||||||
| vli02 | C | |||||||||||||
| wisdompeak | C++ | |||||||||||||
| XiaotaoGuo | C++ | |||||||||||||
| yuanliu666 | Kotlin | |||||||||||||
| YuriSpiridonov | Python | |||||||||||||
| AlgoMonster | C++, Python, Java, TypeScript | |||||||||||||
| WalkCCC | C++, Python, Java | |||||||||||||
| leetcode.ca | C++, C#, Go, Java, PHP, Python, Rust, TypeScript | |||||||||||||
| LeetcodeHelp | C++, Java, Python | |||||||||||||
| MemoryLimitExceeded | Python, C++ | |||||||||||||
| Progiez | C++, Java, Python | |||||||||||||
| AdelDaniel | Dart | |||||||||||||
| aylei | Rust | |||||||||||||
| begeekmyfriend | C | |||||||||||||
| BigEggStudy | C# | |||||||||||||
| black-shadows | C++, C++ | |||||||||||||
| bujosa | Rust | |||||||||||||
| charles-wangkai | Java | |||||||||||||
| chenyanzhe | C++ | |||||||||||||
| everthis | JavaScript | |||||||||||||
| fartem | Ruby | |||||||||||||
| fengvyi | C++ | |||||||||||||
| gaosq0604 | Python | |||||||||||||
| Garvit244 | Python | |||||||||||||
| halfrost | Go | |||||||||||||
| haoel | C++ | |||||||||||||
| JoshCrozier | JavaScript | |||||||||||||
| keineahnung2345 | C++ | |||||||||||||
| lennylxx | C | |||||||||||||
| linouk23 | C++ | |||||||||||||
| lkwq007 | Python | |||||||||||||
| luangong | C++ | |||||||||||||
| MacJim | C++ | |||||||||||||
| qiyuangong | Python | |||||||||||||
| ruoru | Rust | |||||||||||||
| Shamik07 | Dart | |||||||||||||
| shreymehul | C# | |||||||||||||
| sonugiri1043 | C++ | |||||||||||||
| suxrobGM | C# | |||||||||||||
| trung-hn | Python | |||||||||||||
| varunu28 | Java | |||||||||||||
| vli02 | C | |||||||||||||
| wisdompeak | C++ | |||||||||||||
| XiaotaoGuo | C++ | |||||||||||||
| yuanliu666 | Kotlin | |||||||||||||
| YuriSpiridonov | Python |
Videos
Similar Problems
- problem 24: Swap Nodes in Pairs
- problem 1721: Swapping Nodes in a Linked List
- problem 2074: Reverse Nodes in Even Length Groups
Extra
- Tech Stack - my development environment and tools
- AI - how AI helped me create this website (NOT solving the problems)
- Progress - progression over time
- Quality - code quality