重排链表

void reorderList(ListNode *head) {
  if (head->next == nullptr) return;
  // 找中点
  auto m = mid_node(head);
  // 反转后半部分, 中间截断
  ListNode *head2 = reverse(m);
  // 合并链表
  merge_list_node(head, head2);
}

ListNode *mid_node(ListNode *head) {
  ListNode *slow = head;
  ListNode *fast = head;
  while (fast && fast->next) {
    slow = slow->next;
    fast = fast->next->next;
  }
  return slow;
}

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

// 合并 l1 和 l2
void merge_list_node(ListNode *l1, ListNode *l2) {
  while (l2->next) {
    ListNode* nxt = l1->next;
    ListNode* nxt2 = l2->next;
    l1->next = l2;
    l2->next = nxt;
    l1 = nxt;
    l2 = nxt2;
  }
}