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) {}
 * };
 */
   typedef ListNode ln;


   ln *reverse(ln *head)  
   {  
     if(!head || !head->next)return head;  
     ln *prv = NULL, *cur=head, *nxt=head->next;  
     while(cur)  
     {  
       cur->next = prv;  
       prv = cur;  
       cur = nxt;  
       if(nxt)  
         nxt = nxt->next;  
     }  
     return prv;  
   }


  
   void reorderList(ListNode *head) {  
     if(!head || !head->next || !head->next->next)return;  
     ln *fast=head, *slow=head, *prev;  
     while(fast && fast->next)  
     {  
       prev = slow;  
       slow = slow->next;  
       fast = fast->next->next;  
     }  
     if(fast){prev = slow; slow = slow->next;}  
     prev->next = NULL;  
     ln *second = reverse(slow), *first = head;  
     while(first && second)  
     {  
       ln *tmp1 = first->next;  
       ln *tmp2 = second->next;  
       first->next = second;  
       second->next = tmp1;  
       second = tmp2;  
       first = tmp1;  
     }  
   }