2074. Reverse Nodes in Even Length Groups

• Time: $O(n)$
• Space: $O(1)$

C++JavaPython

class Solution {
 public:
  ListNode* reverseEvenLengthGroups(ListNode* head) {
    // prev -> (head -> ... -> tail) -> next -> ...
    ListNode dummy(0, head);
    ListNode* prev = &dummy;
    ListNode* tail = head;
    ListNode* next = head->next;
    int groupLength = 1;

    while (true) {
      if (groupLength % 2 == 1) {
        prev->next = head;
        prev = tail;
      } else {
        tail->next = nullptr;
        prev->next = reverse(head);
        // Prev -> (tail -> ... -> head) -> next -> ...
        head->next = next;
        prev = head;
      }
      if (next == nullptr)
        break;
      head = next;
      const auto [theTail, theLength] = getTailAndLength(head, groupLength + 1);
      tail = theTail;
      next = tail->next;
      groupLength = theLength;
    }

    return dummy.next;
  }

 private:
  pair<ListNode*, int> getTailAndLength(ListNode* head, int groupLength) {
    int length = 1;
    ListNode* tail = head;
    while (length < groupLength && tail->next) {
      tail = tail->next;
      ++length;
    }
    return {tail, length};
  }

  ListNode* reverse(ListNode* head) {
    ListNode* prev = nullptr;
    while (head) {
      ListNode* next = head->next;
      head->next = prev;
      prev = head;
      head = next;
    }
    return prev;
  }
};

class Solution {
  public ListNode reverseEvenLengthGroups(ListNode head) {
    // prev -> (head -> ... -> tail) -> next -> ...
    ListNode dummy = new ListNode(0, head);
    ListNode prev = dummy;
    ListNode tail = head;
    ListNode next = head.next;
    int groupLength = 1;

    while (true) {
      if ((groupLength & 1) == 1) {
        prev.next = head;
        prev = tail;
      } else {
        tail.next = null;
        prev.next = reverse(head);
        // Prev -> (tail -> ... -> head) -> next -> ...
        head.next = next;
        prev = head;
      }
      if (next == null)
        break;
      head = next;
      Pair<ListNode, Integer> res = getTailAndLength(head, groupLength + 1);
      tail = res.getKey();
      next = tail.next;
      groupLength = res.getValue();
    }

    return dummy.next;
  }

  private Pair<ListNode, Integer> getTailAndLength(ListNode head, int groupLength) {
    int length = 1;
    ListNode tail = head;
    while (length < groupLength && tail.next != null) {
      tail = tail.next;
      ++length;
    }
    return new Pair<>(tail, length);
  }

  ListNode reverse(ListNode head) {
    ListNode prev = null;
    while (head != null) {
      ListNode next = head.next;
      head.next = prev;
      prev = head;
      head = next;
    }
    return prev;
  }
}

class Solution:
  def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:
    # prev -> (head -> ... -> tail) -> next -> ...
    dummy = ListNode(0, head)
    prev = dummy
    tail = head
    next = head.next
    groupLength = 1

    def getTailAndLength(head: Optional[ListNode], groupLength: int) -> Tuple[Optional[ListNode], int]:
      length = 1
      tail = head
      while length < groupLength and tail.next:
        tail = tail.next
        length += 1
      return tail, length

    def reverse(head: Optional[ListNode]) -> Optional[ListNode]:
      prev = None
      while head:
        next = head.next
        head.next = prev
        prev = head
        head = next
      return prev

    while True:
      if groupLength & 1:
        prev.next = head
        prev = tail
      else:
        tail.next = None
        prev.next = reverse(head)
        # Prev -> (tail -> ... -> head) -> next -> ...
        head.next = next
        prev = head
      if not next:
        break
      head = next
      tail, length = getTailAndLength(head, groupLength + 1)
      next = tail.next
      groupLength = length

    return dummy.next