第一次代码：
class Solution {public: void reorderList(ListNode *head) { if(head == NULL || head->next == NULL) return ; ListNode* slow = head; ListNode* fast = head; do{ slow = slow->next; fast = fast->next->next; }while(fast != NULL && fast->next != NULL); //把整个链表划分成2个等长的子链表，如果原链表长度为奇数，那么第一个子链表的长度多1 ListNode* head1 = head; ListNode* head2 = slow->next; slow->next = NULL; ListNode* cur = head2; ListNode* next = cur->next; ListNode* PRev = NULL; while(cur != NULL){ next = cur->next; cur->next = prev; prev = cur; cur = next; } head2 = prev; ListNode* next2 = NULL; while(head2 != NULL){ next = head1->next; next2 = head2->next; head1->next = head2; head2->next = next; head1 = next; head2 = next2; } }};要注意在中断点将两部分都复制为NULL，否则可能会输出太多内容。
上面的代码可读性甚好，但是申请的变量有点多。下面优化了一下，不过到底哪种风格好，还是各有千秋吧。
class Solution {public: void reorderList(ListNode* head) { if(head == NULL || head->next == NULL) return ; ListNode* n1 = head; ListNode* n2 = head; do{ n1 = n1->next; n2 = n2->next->next; }while(n2 != NULL && n2->next != NULL); ListNode* n3 = n1->next; n1->next = NULL; n1 = NULL, n2 = n3; while(n2 != NULL){ n3 = n2->next; n2->next = n1; n1 = n2; n2 = n3; } ListNode* n4 = n1; n1 = head, n3 = n4; while(n3 != NULL){ n2 = n1->next; n4 = n3->next; n1->next = n3; n3->next = n2; n1 = n2; n3 = n4; } }};回过头来重新做一遍，使用二级指针+deque：
class Solution {public: void reorderList(ListNode* head) { if(head == NULL) return ; ListNode** pp = &(head->next); ListNode* tmp = head->next; std::deque<ListNode*> deq; while(tmp != NULL){ deq.push_back(tmp); tmp = tmp->next; } bool even = true; while(!deq.empty()){ if(even){ tmp = deq.back(); deq.pop_back(); } else{ tmp = deq.front(); deq.pop_front(); } *pp = tmp; pp = &(tmp->next); tmp->next = NULL; even = !even; } }};新闻热点
疑难解答
