/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode * reverse(struct ListNode * head)
{
    struct ListNode Head,*tmp;
    Head.next = NULL;
    while(head)
    {
        tmp = head;
        head = head->next;
        tmp->next = Head.next;
        Head.next = tmp;
    }
    return Head.next;
}
void reorderList(struct ListNode* head) {
    struct ListNode Head,*fast,*slow,*last;
    Head.next = head;
    last = &Head;
    slow = fast = head;
    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    if(fast)
    {
        fast = slow;
        slow = slow->next;
        fast->next = NULL;
    }
    slow = reverse(slow);
    while(slow)
    {
        last->next = head;
        last = head;
        head = head->next;
        last->next = slow;
        last = slow;
        slow = slow ->next;
    }
    last->next = fast;
}