# 2074. Reverse Nodes in Even Length Groups

• Time: $O(n)$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 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 & 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 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; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 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 res = getTailAndLength(head, groupLength + 1); tail = res.getKey(); next = tail.next; groupLength = res.getValue(); } return dummy.next; } private Pair 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; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 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