Today I have done leetcode's December LeetCoding Challenge with cpp.

December LeetCoding Challenge 22

Description

Reorder List

You are given the head of a singly linked-list. The list can be represented as:

L0 → L1 → … → Ln - 1 → Ln

Reorder the list to be on the following form:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

You may not modify the values in the list's nodes. Only nodes themselves may be changed.

Example 1:

Input: head = [1,2,3,4]
Output: [1,4,2,3]

Example 2:

Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]

Constraints:

• The number of nodes in the list is in the range [1, 5 * 104].
• 1 <= Node.val <= 1000

You are given the head of a singly linked-list. The list can be represented as:

L0 → L1 → … → Ln - 1 → Ln

Reorder the list to be on the following form:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

You may not modify the values in the list's nodes. Only nodes themselves may be changed.

Example 1:

Input: head = [1,2,3,4]
Output: [1,4,2,3]

Example 2:

Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]

Constraints:

• The number of nodes in the list is in the range [1, 5 * 104].
• 1 <= Node.val <= 1000

Solution

auto speedup = [](){
  cin.tie(nullptr);
  cout.tie(nullptr);
  ios::sync_with_stdio(false);
  return 0;
}();
class Solution {
  int length(ListNode *head) {
    int result = 0;
    while(head) {
      result += 1;
      head = head->next;
    }
    return result;
  }
  ListNode *advance(ListNode *head, int count) {
    while(--count) {
      head = head->next;
    }
    return head;
  }
  ListNode *reverse(ListNode *head) {
    ListNode *tail = nullptr;
    while(head) {
      ListNode *tmp = head->next;
      head->next = tail;
      tail = head;
      head = tmp;
    }
    return tail;
  }
  void merge(ListNode *head1, ListNode *head2) {
    while(head1 && head2) {
      ListNode *tmp2 = head2->next;
      head2->next = head1->next;
      head1->next = head2;
      head1 = head2->next;
      head2 = tmp2;
    }
  }
public:
  void reorderList(ListNode* head) {
    int len = length(head);
    ListNode *tail1 = advance(head, (len + 1) / 2);
    ListNode *head2 = tail1->next;
    tail1->next = nullptr;
    head2 = reverse(head2);
    merge(head, head2);
  }
};

// Accepted
// 12/12 cases passed (32 ms)
// Your runtime beats 95.77 % of cpp submissions
// Your memory usage beats 76.71 % of cpp submissions (17.8 MB)