Problem 25

Abstract / Summary

Reverse groups of k nodes in a linked list by reversing each group without changing the order of the groups.

Note

The full problem description, including helpful examples, can be found on LeetCode.

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
45 lines | 1190 bytes | submitted August 25, 2023 | GitHub   5% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 67% (2+ million submissions).

Typical patterns to solve this problem:
  • Linked List
  • Recursion
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
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.
LeetCode profile | GitHub repo

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.

written by openai gpt

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.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 29 | median = 5 | μ = 5.17 | σ = 1.68

Complexity Analysis

not analyzed yet

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
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
58 links | 41 authors | 13 languages

Videos

These are a few popular YouTube videos for this problem:
YouTube video 'Reverse Nodes in K-Group - Linked List - Leetcode 25'
NeetCode 13 mins
Reverse Nodes in K-Group - Linked List - Leetcode 25
YouTube video 'Reverse Nodes in k-Group O(1) | Live Coding with Explanation | Leetcode - 25'
Algorithms Made Easy 16 mins
Reverse Nodes in k-Group O(1) | Live Coding with Explanation | Leetcode - 25
YouTube video 'Reverse Nodes in k-Group | LeetCode 25 | C++ 🕵️‍♂️🔥'
Knowledge Center 28 mins
Reverse Nodes in k-Group | LeetCode 25 | C++ 🕵️‍♂️🔥
YouTube video 'Reverse Nodes in k-Group leetcode solution in hindi'
Engineering Digest 13 mins
Reverse Nodes in k-Group leetcode solution in hindi
YouTube video 'REVERSE NODES IN K GROUP | LEETCODE 25 | PYTHON SOLUTION'
Cracking FAANG 19 mins
REVERSE NODES IN K GROUP | LEETCODE 25 | PYTHON SOLUTION
YouTube video 'Reverse Nodes in k-Group Python Solution - LeetCode #25'
Professor Oakes 8 mins
Reverse Nodes in k-Group Python Solution - LeetCode #25
YouTube video 'Reverse Nodes in k-Group LeetCode 25 | Easy & Clear Explanation for Beginners'
CodingNinja 13 mins
Reverse Nodes in k-Group LeetCode 25 | Easy & Clear Explanation for Beginners
YouTube video 'Reverse Nodes in k-Group || Linked List 15 || Placement Preparation Series || LeetCode 25 || Hard ||'
Bro Coders 12 mins
Reverse Nodes in k-Group || Linked List 15 || Placement Preparation Series || LeetCode 25 || Hard ||
YouTube video 'Reverse Nodes in K Group ( Leetcode 25 ) || Day -2 DSA Challenge || DSA Practice Series #dsa #coding'
ExamPrepTool 42 mins
Reverse Nodes in K Group ( Leetcode 25 ) || Day -2 DSA Challenge || DSA Practice Series #dsa #coding
YouTube video 'Daily Leetcode #474: Jul 18, 2021 - 25. Reverse Nodes in k-Group'
Programming Live with Larry 18 mins
Daily Leetcode #474: Jul 18, 2021 - 25. Reverse Nodes in k-Group
YouTube video '25. Reverse Nodes in k-Group (Leetcode Hard)'
Programming Live with Larry 34 mins
25. Reverse Nodes in k-Group (Leetcode Hard)
YouTube video 'Reverse Nodes in k-Group | LeetCode 25 | Google Interview Question'
Sanyam IIT Guwahati 15 mins
Reverse Nodes in k-Group | LeetCode 25 | Google Interview Question
YouTube video 'Leetcode Question 25 "Reverse Nodes in k-Group" in Javascript'
Ghumman Tech 9 mins
Leetcode Question 25 "Reverse Nodes in k-Group" in Javascript
YouTube video 'LeetCode 25 | Reverse Nodes in k-Group | Reverse, Recursion | Java'
Sleepy Cracker 6 mins
LeetCode 25 | Reverse Nodes in k-Group | Reverse, Recursion | Java
YouTube video '44. Leetcode 25. Reverse Nodes in k-Group : Javascript'
Web Fusion with Bharadwaj 18 mins
44. Leetcode 25. Reverse Nodes in k-Group : Javascript
YouTube video 'Reverse Nodes in k-Group - LeetCode #25 - C++'
Sean Chuah 10 mins
Reverse Nodes in k-Group - LeetCode #25 - C++
YouTube video '25. Reverse Nodes in k-Group | Leetcode | Python'
Abdullah Arshed 22 mins
25. Reverse Nodes in k-Group | Leetcode | Python
YouTube video 'Amazon Software Engineer Interview Preparation - Part 24 LC  25 Reverse Nodes in k-Group'
Ghumman Tech 13 mins
Amazon Software Engineer Interview Preparation - Part 24 LC 25 Reverse Nodes in k-Group
YouTube video 'Reverse Nodes in k-Group'
Alpha-Code 13 mins
Reverse Nodes in k-Group
YouTube video '86. Leetcode 25. Reverse Nodes in k-Group : JAVA'
Web Fusion with Bharadwaj 16 mins
86. Leetcode 25. Reverse Nodes in k-Group : JAVA
20 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

3 similar problems

Extra

There are a few extra pages giving you some insights into my setup:
  • 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