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;

        }

        

    }

};