/**

 * 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 == NULL) return;

        ListNode *p1, *p2, *p3, *head2;

        p1 = p2 = head;

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

            p1 = p1->next;

            p2 = p2->next->next;

        }

        head2 = p1->next; p1 = p1->next = NULL;

        p2 = head2;

        while(p2) {

            p3 = p2->next;

            p2->next = p1;

            p1 = p2;

            p2 = p3;

        }

        head2 = p1; p1 = head;

        while(head2 && p1) {

            p2 = head2->next;

            head2->next = p1->next;

            p1->next = head2;

            head2 = p2;

            p1 = p1->next->next;

        }

    }

};