#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
void reorderList(ListNode *head) {
ListNode * p0 = head;
ListNode * p = head;
if( !(p != NULL && p->next != NULL && p->next->next != NULL)){
//
return;
}
//
while( p->next!= NULL && p->next->next != NULL){
p0 = p0->next;
p = p->next->next;
}
//
p = p0->next;
p0->next = NULL;
//
ListNode *t = p;
p = p->next;
t->next = NULL;//
while(p != NULL){
ListNode *tt = p->next;
p->next = t;
t = p;
p = tt;
}
p = t;
// 。
ListNode *tt;
p0 = head;
while( p0 != NULL && p!= NULL){
t = p0->next;
tt = p->next;
p0->next = p;
p->next = t;
p0 = t;
p = tt;
}
}
};
int main()
{
Solution ss;
ListNode *head = new ListNode(1);
ListNode *p = head;
int n = 2;
while( n != 6)
{
p->next = new ListNode(n++);
p = p->next;
}
ss.reorderList(head);
return 0;
}