/** * 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; } };