Leetcode #2074: Reverse Nodes in Even Length Groups
In this guide, we solve Leetcode #2074 Reverse Nodes in Even Length Groups 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
You are given the head of a linked list. The nodes in the linked list are sequentially assigned to non-empty groups whose lengths form the sequence of the natural numbers (1, 2, 3, 4, ...).
Quick Facts
- Difficulty: Medium
- Premium: No
- Tags: 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 = [5,2,6,3,9,1,7,3,8,4]
Output: [5,6,2,3,9,1,4,8,3,7]
Explanation:
- The length of the first group is 1, which is odd, hence no reversal occurs.
- The length of the second group is 2, which is even, hence the nodes are reversed.
- The length of the third group is 3, which is odd, hence no reversal occurs.
- The length of the last group is 4, which is even, hence the nodes are reversed.
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 reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:
def reverse(head, l):
prev, cur, tail = None, head, head
i = 0
while cur and i < l:
t = cur.next
cur.next = prev
prev = cur
cur = t
i += 1
tail.next = cur
return prev
n = 0
t = head
while t:
t = t.next
n += 1
dummy = ListNode(0, head)
prev = dummy
l = 1
while (1 + l) * l // 2 <= n and prev:
if l % 2 == 0:
prev.next = reverse(prev.next, l)
i = 0
while i < l and prev:
prev = prev.next
i += 1
l += 1
left = n - l * (l - 1) // 2
if left > 0 and left % 2 == 0:
prev.next = reverse(prev.next, left)
return dummy.next
Complexity
The time complexity is O(n). The space complexity is O(1).
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.