/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

typedef ListNode Node;
Node* FindMid(Node* h)
{
    Node *p = h, *q = h->next;
    while (q && q->next)
    {
        p = p->next;
        q = q->next;
        if (q->next) q = q->next;
    }
    return p;
}

void Reverse(Node* p)
{
    Node* q = p->next;
    p->next = 0;
    while (q)
    {
        Node* r = q->next;
        q->next = p->next;
        p->next = q;
        q = r;
    }
}

class Solution {
public:
    void rearrangedList(ListNode* head) {
        Node* mid = FindMid(head);
        Reverse(mid);
        Node* p = head->next;
        Node* q = mid->next;
        Node* r = head;
        mid ->next = 0;
        if (q)
        {
            r->next = q;
            q = q->next;
            r=r->next;
        }
        while (p&&q)
        {
            r ->next = p;
            p = p->next;
            r = r->next;
            r->next = q;
            q = q->next;
            r = r->next;
        }
        r->next = p? p: q;
    }
};