[LeetCode] Reorder List

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes' values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

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

    ListNode *reverse(ListNode *p)
    {
        ListNode *ret = NULL;
        while(p)
        {
            ListNode * t =p->next;
            p->next = ret;
            ret = p;
            p = t;
        }
        return ret;
    }

    void reorderList(ListNode *head) {
        if(!head) return;
        int c = 0;
        ListNode *p = head, *m=head;
        ListNode *prev = head;
        while(p)
        {
            p=p->next;
            c++;
            if(c%2==0)
            {
                prev = m;
                m=m->next;
            }
        }
        if(c<=2) return;
        
        prev->next = NULL;
        ListNode *r = reverse(m);
        p = head;
        ListNode dummy(0);
        ListNode *ret = &dummy;
        c = 0; 
        while(p&&r)
        {
            if(c%2 ==0)
            {
                ret->next = p;
                ret = p;
                p = p->next;
            }
            else
            {
                ret->next = r;
                ret = r;
                r = r->next;
            }
            c++;
        }
        if(p) ret->next = p;
        else ret->next = r;
    }
};