reorder List

/**
 * 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) {
        ListNode *slow;
        ListNode *fast;

        if(head == NULL || head->next ==NULL || head->next->next==NULL) return;
        //统计链表长度n
        slow = head;
        int n=0;
        while(slow){
            slow = slow->next;
            n++;
        }
        //走一半，寻找下一半fast的开始位置
        int i=0;
        slow=head;
        while(i<(n-1)/2){
            slow=slow->next;
            i++;
        }
        fast = slow->next;
        slow->next = NULL;
        
        //inverse the fast seq
        ListNode * pre=NULL,*cur=fast,*next;
        while(cur)
        {
            next=cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        
        //merge two list
        fast = pre;
        slow = head;
        while(slow){
            next=slow->next;
            if(fast)
            {   slow->next = fast;
                ListNode* temp = fast->next;
                fast->next = next;
                fast = temp;
            
            }
            slow = next;
        }
        
    }
};