Leetcode #25: Reverse Nodes in k-Group
In this guide, we solve Leetcode #25 Reverse Nodes in k-Group in Python and focus on the core idea that makes the solution efficient.
You will see the intuition, the step-by-step method, and a clean Python implementation you can use in interviews.
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.
Quick Facts
- Difficulty: Hard
- Premium: No
- Tags: Recursion, Linked List
Intuition
Linked list problems often require pointer manipulation rather than extra memory.
Two-pointer techniques expose cycles, midpoints, or reordering patterns.
Approach
Traverse with fast/slow pointers or reverse sublists when needed.
Maintain invariants carefully to avoid losing nodes.
Steps:
- Traverse with pointers.
- Reverse or split if required.
- Reconnect nodes correctly.
Example
Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]
Python Solution
# 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]:
def reverse(head: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode()
cur = head
while cur:
nxt = cur.next
cur.next = dummy.next
dummy.next = cur
cur = nxt
return dummy.next
dummy = pre = ListNode(next=head)
while pre:
cur = pre
for _ in range(k):
cur = cur.next
if cur is None:
return dummy.next
node = pre.next
nxt = cur.next
cur.next = None
pre.next = reverse(node)
node.next = nxt
pre = node
return dummy.next
Complexity
The time complexity is , where is the length of the linked list. The space complexity is .
Edge Cases and Pitfalls
Watch for boundary values, empty inputs, and duplicate values where applicable. If the problem involves ordering or constraints, confirm the invariant is preserved at every step.
Summary
This Python solution focuses on the essential structure of the problem and keeps the implementation interview-friendly while meeting the constraints.