leetcode 重排链表 中等

class Solution {
public:
    void reorderList(ListNode* head) {
        ListNode *tail = reverseHalfList(head);
        ListNode *ptr = head;
        while(tail) {      // tail 为 nullptr, 整个链接就完成了.
            ListNode *ptrNext = ptr -> next;
            ListNode *tailLast = tail -> next;
            ptr -> next = tail;
            tail -> next = ptrNext;
            ptr = ptrNext;
            tail = tailLast;
        }
    }

private:
    ListNode* reverseHalfList(ListNode *head) {
        ListNode *slow = head, *quick = head;
        // 寻找链表中间节点
        // 链表结点为单数, slow 停止中间节点. 为偶数 slow 停止在中间第一个结点
        while(quick && quick -> next && quick -> next -> next) {
            slow = slow -> next;
            quick = quick -> next -> next;
        }

        ListNode *slowNext = slow -> next;
        slow -> next = nullptr;
        return reverseList(slowNext);
    }

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