class Solution {

public:

void reorderList(ListNode* head) {

ListNode *head1 = head, *head2 = NULL;

int len = 0, count = 1;

while(head) { //遍历链表

head = head -> next;

++len;

}

head = head1;

if(len <= 2 || !head)

return;

while(count != ceil(len / 2.0)) { /*把链表切成两段h1 h2 */

head = head -> next;

++count;

}

head2 = head -> next;

head -> next = NULL;

head = head1;

head2 = reverse(head2);//reverse head2

for(ListNode *i = head1, *j = head2; i&&j; head1 = i, head2 = j) {//i和j存之后的两个链表节点  最初判断条件只有i 不是i&&j 这样导致后面调用head2 -》next时候head2可能为null越界

if(head1 -> next)

i = head1 -> next;

else

i = NULL;

head1 -> next = head2;

if(head2 -> next)

j = head2 -> next;

else

j = NULL;

head2 -> next = i;

}

return;

}

ListNode *reverse(ListNode * head) {

ListNode *t, *y = head, *r = NULL;

if(head -> next == NULL)

return head;

while(y != NULL) {

t = y -> next;

y -> next = r;

r = y;

y = t;

}

return r;

}

};