LeetCode 2074: Reverse Nodes in Even Length Groups

Two pass

We first collect the groups in a list and then connect the groups. If a group has even size we also reverse it.

Time: $\mathcal{O}(n)$ , space: $\mathcal{O}(n)$ .

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def get_next_group(self, head, size):
        group = []
        while head and size > 0:
            group.append(head)
            head = head.next
            size -= 1
        if group:
            group[-1].next = None

        return group, head

    def reverse(self, group):
        group.reverse()
        for i in range(len(group)-1):
            group[i].next = group[i+1]
        group[-1].next = None

    def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:
        groups = []
        group_size = 1
        curr_head = head
        while curr_head:
            group, curr_head = self.get_next_group(curr_head, group_size)
            groups.append(group)
            group_size += 1

        for i in range(1, len(groups)):
            prev_group = groups[i-1]
            curr_group = groups[i]
            if len(curr_group) % 2 == 0:
                self.reverse(curr_group)
            prev_group[-1].next = curr_group[0]

        return head

One pass

For the groups we have two types of operations:

Odd-sized group: Skip ahead by the expected group size number of nodes.
Even-sized group: Reverse the expected group size number of nodes.

If the count of nodes processed by an operation is smaller than the expected group size, we know it is a tail group and we may need some fixing. If we expected the tail group to have odd size but only even number of nodes remain, we need to reverse them. On the other hand, if we expected the tail group to have even size but only odd number of nodes remain, we need to restore the order by reversing.

Time: $\mathcal{O}(n)$ , space: $\mathcal{O}(1)$ .

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def skip(self, head, size):
        m = 0
        prev, curr = None, head
        while curr and size > 0:
            prev = curr
            curr = curr.next
            size -= 1
            m += 1

        return prev, curr, m

    def reverse(self, head, reverse_count):
        m = 0
        prev, curr = None, head
        while curr and reverse_count > 0:
            next = curr.next
            curr.next = prev
            prev = curr
            curr = next

            reverse_count -= 1
            m += 1

        return prev, curr, m

    def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:
        is_odd = lambda n: n % 2 == 1

        group_size = 1
        prev_tail = None
        curr_head = head
        while True:
            if is_odd(group_size):
                tail, next_head, node_count = self.skip(curr_head, group_size)
                if node_count < group_size:
                    # tail group
                    if not is_odd(node_count):
                        # even number of nodes remaining
                        reversed_head, next_head, reverse_count = self.reverse(
                            curr_head, node_count
                        )
                        if prev_tail:
                            prev_tail.next = reversed_head
                    break
                prev_tail = tail
                curr_head = next_head
            else:
                reversed_head, next_head, reverse_count = self.reverse(
                    curr_head, group_size
                )
                if reverse_count < group_size:
                    # tail group
                    if is_odd(reverse_count):
                        # odd number of nodes remaining, restore order
                        self.reverse(reversed_head, reverse_count)
                    else:
                        if prev_tail:
                            prev_tail.next = reversed_head
                    break

                if prev_tail:
                    prev_tail.next = reversed_head
                prev_tail = curr_head
                curr_head.next = next_head
                curr_head = next_head

            group_size += 1

        return head

unreasonably effective