反转链表+双指针

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
ListNode * reverse( ListNode * root )
{
    if( nullptr==root || nullptr==root->next )
    {
        return root;
    }

    ListNode * sentry=nullptr;
    while( nullptr!=root )
    {
        ListNode * temp=root->next;
        root->next=sentry;
        sentry=root;
        root=temp;
    }
    return sentry;
}
class Solution {
public:
    void reorderList(ListNode *head) {

        if( nullptr==head || nullptr==(head->next) )
        {
            return ;
        }

        ListNode * low=head;
        ListNode * fast=head;
        while( 1 )
        {
            fast=fast->next;
            if( nullptr==fast ) break;
            fast=fast->next;
            if( nullptr==fast ) break;
            low=low->next;
        }

        ListNode * first=head;
        ListNode * ttt=low->next;
        low->next=nullptr;

        ListNode * second=reverse( ttt );

        ListNode * sentry=new ListNode(-1);
        ListNode * temp=sentry;

        while( nullptr!=first && nullptr!=second )
        {
            sentry->next=first;
            sentry=sentry->next;
            //sentry->next=nullptr;
            first=first->next;

            sentry->next=second;
            sentry=sentry->next;
            //sentry->next=nullptr;
            second=second->next;

        }

        if( nullptr!=first )
        {
            sentry->next=first;
            sentry=sentry->next;
            sentry->next=nullptr;
        }



        head=temp->next;

        delete temp;
        return;
    }
};