【面试系列】重排链表

题意：
原题链接

思路：

• 快慢指针找到中点（或者先遍历得到长度，再遍历一半也可行）
• 反转后半部分
• 归并两部分

代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    
    ListNode* reverseList(ListNode* head) {
        if(head == NULL || head->next == NULL) return head;
        ListNode *next_tail = head->next;
        ListNode *next_head = reverseList(head->next);
        next_tail->next = head;
        head->next = NULL;
        return next_head;
    }
    
    void reorderList(ListNode* head) {
        ListNode *dummy = new ListNode(-1);
        dummy->next = head;
        ListNode *quick = dummy, *slow = dummy;
        while(quick) {
            if(quick) quick = quick->next;
            if(quick) quick = quick->next;
            if(slow) slow = slow->next;
        }
        ListNode *second = reverseList(slow->next);
        ListNode *first = head;
        slow->next = NULL;
        
        ListNode *tmp = dummy;
        while(first) {
            tmp->next = first;
            tmp = tmp->next;
            first = first->next;
            if(second) {
                tmp->next = second;
                tmp = tmp->next;
                second = second->next;
            }
        }    
    }
};