How hard is LeetCode 2074. Reverse Nodes in Even Length Groups?

LeetCode 2074. Reverse Nodes in Even Length Groups is rated Medium on LeetCode.

What is the time complexity of LeetCode 2074. Reverse Nodes in Even Length Groups?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 2074. Reverse Nodes in Even Length Groups?

The Python solution on this page uses O(1) auxiliary space.

What topics does LeetCode 2074. Reverse Nodes in Even Length Groups cover?

LeetCode 2074. Reverse Nodes in Even Length Groups is tagged Linked List on LeetCode.

Reverse Nodes in Even Length Groups — LeetCode 2074 Python Solution

MediumLinked List

Problem: #2074
Pattern: Linked List
Reading time: 7 min
Source: leetcode.com

The problem

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, ...).

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.

Python solution

Python

# 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

Measure	Complexity
Time	O(n)
Space	O(1) auxiliary

Pattern: Linked List

Rewire pointers in place, with a dummy head and a saved next to keep it safe. LeetCode 2074. Reverse Nodes in Even Length Groups is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Linked List.

The linked list guide has the Python template for the pattern and the 75 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2074. Reverse Nodes in Even Length Groups?: LeetCode 2074. Reverse Nodes in Even Length Groups is rated Medium on LeetCode.
What is the time complexity of LeetCode 2074. Reverse Nodes in Even Length Groups?: The Python solution on this page runs in O(n).
What is the space complexity of LeetCode 2074. Reverse Nodes in Even Length Groups?: The Python solution on this page uses O(1) auxiliary space.
What topics does LeetCode 2074. Reverse Nodes in Even Length Groups cover?: LeetCode 2074. Reverse Nodes in Even Length Groups is tagged Linked List on LeetCode.