/**

  * Definition for singly-linked list.

  * struct ListNode {

  *     int val;

  *     ListNode *next;

  *     ListNode(int x) : val(x), next(NULL) {}

  * };

  */

 class Solution {

 public:

     void reorderList(ListNode *head) {

         if (head == nullptr || head->next == nullptr || head->next->next == nullptr) {

             return;

         }

         ListNode *fast = head, *slow = head;

         while (fast->next && fast->next->next) {

             fast = fast->next->next;

             slow = slow->next;

         }

         fast = slow->next;

         slow->next = nullptr;

         fast = reverseList(fast);

         head = mergeList(head, fast);

     }

 private:

     ListNode * reverseList(ListNode *head) {

         ListNode dummy(-);

         ListNode *p = &dummy;

         while (head) {

             ListNode *temp = head->next;

             head->next = p->next;

             p->next = head;

             head = temp;

         }

         return dummy.next;

     }

     ListNode *mergeList(ListNode *l1, ListNode *l2) {

         ListNode dummy(-);

         ListNode *p = &dummy;

         while (l1) {

             p->next = l1;

             l1 = l1->next;

             p = p->next;

             if (l2) {

                 p->next = l2;

                 l2 = l2->next;

                 p = p->next;

             }

         }

         return dummy.next;

     }

 };