Reorder List

    void reorderList(ListNode *head) {
        if (head == NULL || head->next == NULL) return;
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast != NULL && fast->next != NULL) {
            fast = fast->next->next;
            slow = slow->next;
        }
        ListNode* reverseHead = slow->next;           // find the second half of list
        slow->next = NULL;                           // make first half end point to null
        reverseHead = reverse(reverseHead);         // reverse second half    
        ListNode* cur = head;       
        while(reverseHead != NULL) {                // link together
            ListNode* tmp = reverseHead->next;
            reverseHead->next = cur->next;
            cur->next = reverseHead;
            cur = cur->next->next;
            reverseHead = tmp;
        }
    }
   
    ListNode* reverse(ListNode* head) {
        if (head == NULL || head->next == NULL) return head;
        ListNode dummy(0);
        dummy.next = head;
        head = &dummy;
        ListNode* cur = head->next;
        while(cur->next != NULL) {
            ListNode* tmp = cur->next;
            cur->next = tmp->next;
            tmp->next = head->next;
            head->next = tmp;
        }
        return head->next;
    }