https://leetcode.com/problems/reorder-list/
先找链表中点，然后把右边反转，再按要求重构链表。
class Solution { public:void reorderList(ListNode* head) {if (!head || !head->next) return;ListNode *mid = find_mid(head);ListNode *right = mid->next; mid->next = NULL;right = reverse_list(right);ListNode dummy(0), *cur = &dummy;bool is_odd = true;while (head && right) {if (is_odd) { cur->next = head; head = head->next; }else { cur->next = right; right = right->next; }cur = cur->next;is_odd = !is_odd;}cur->next = head ? head : right;return;}ListNode* find_mid(ListNode* head) {ListNode *slow = head, *fast = head->next;while (fast && fast->next) {slow = slow->next;fast = fast->next->next;}return slow;}ListNode* reverse_list(ListNode* head) {ListNode *prev = NULL;while (head) {ListNode *next = head->next;head->next = prev;prev = head;head = next;}return prev;} };