Given a singly linked list L: L0→ L1→ … → Ln-1→ Ln

reorder it to: L0→ Ln→ L1→ Ln-1→ L2→ Ln-2→ …

Example

Given1->2->3->4->null, reorder it to1->4->2->3->null.

/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @return: void
     */
    void reorderList(ListNode *head) {
        if (head == NULL || head->next == NULL) {
            return;
        }

        ListNode* middle = findMiddle(head);
        ListNode* right = reverseList(middle->next);
        middle->next = NULL;
        merge(head, right);
        return;
    }
    ListNode* findMiddle(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head->next;
        while (fast != NULL && fast->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = NULL;
        while (head != NULL) {
            ListNode* temp = head->next;
            head->next = pre;
            pre = head;
            head = temp;
        }
        return pre;
    }
    void merge (ListNode* head, ListNode* right) {
        ListNode* dummy = new ListNode (0);
        ListNode* cur = dummy;
        int count = 0;
        while (head != NULL && right != NULL) {
            if (count%2 == 0) {
                cur->next = head;
                head = head->next;
            } else {
                cur->next = right;
                right = right->next;
            }
            cur = cur->next;
            count++;
        }
        if (head != NULL) {
            cur->next = head;
        } else if (right != NULL) {
            cur->next = right;
        }
        return;
    }
};