< Back





2074. Reverse Nodes in Even Length Groups

The most difficult part about this problem is grouping together the nodes in even length that need to
be reversed while also managing the last group that may not be the same length as the current group
length requirement.

What we do to easily solve this is maintain a connector node, this will always be the node preceding
the segment to be reversed. We modify our reversal method slightly to account for the fact that prev
will point to the connector node. We also maintain a tail node that will be the last node of the
newly reversed segment. In this modified reversal method, curr will end up being the next node after
the segmnet, allowing us to easily link the tail of the segment to the succeeding nodes.

We only reverse a segment of nodes if the number of nodes we've encountered is the same as the size
of the group, or if curr.next is None - meaning we've reached the last group. We then check to see if
the number of nodes we've encountered is even. If so, we reverse the segment and set curr to the tail
of the reversed segment.

Then the connector node is set to curr, we increment the group because we're starting the next one,
and we reset the nodes encountered to 0. curr will continue to iterate, and we'll continue to count
the number of nodes encountered.

The solution is as follows:


  class Solution:
      def reverseBetween(self, sentinel: ListNode, n: int) -> ListNode:
          prev = sentinel
          curr = sentinel.next
          tail = sentinel.next

          for _ in range(n):
              next_node = curr.next
              curr.next = prev
              prev = curr
              curr = next_node

          sentinel.next = prev
          tail.next = curr
          return tail

      def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:
          conn = None
          curr = head
          group = 1
          node_count = 1

          while curr:
              if group == node_count or not curr.next:
                  if not node_count % 2:
                      curr = self.reverseBetween(connector, node_count)
                  connector = curr
                  group += 1
                  node_count = 0

              node_count += 1
              curr = curr.next

          return head


_ Time Complexity:

  O(n) - We traverse all nodes within the linked list.

_ Space Complexity:

  O(1) - We maintain pointers that occupy constant space.