题目：
Given a singly linked list→…→,reorder it to:→-1→-2→…
You must do this in-place without altering the nodes’ values.
For example,Given{1,2,3,4}, reorder it to{1,4,2,3}.
思路：利用快慢两个指针将链表一分为二，针对第二个子链表求倒序，最后将两个子链表合并。
#include <iostream>#include <vector>using namespace std;/* Given a singly linked list L: L0→L1→…→Ln-1→Ln,reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…You must do this in-place without altering the nodes' values.For example,Given {1,2,3,4}, reorder it to {1,4,2,3}.*/typedef struct list_node List;struct list_node{struct list_node* next;int value;};void print_list(List* list){List* tmp=list;while(tmp != NULL){cout<<tmp->value<<endl;tmp = tmp->next; }}/*初始化List 将从1~n的数字插入到链表中 */void Init_List(List*& head,int* array,int n){head = NULL;List* tmp;List* record;for(int i=1;i<=n;i++){tmp = new List;tmp->next = NULL;tmp->value = array[i-1];if(head == NULL){head = tmp;record = head;}else{record->next = tmp;record = tmp;}}}int Len_list(List* list){if(list == NULL)return 0;elsereturn Len_list(list->next)+1;}/*重新排序链表 将一个链表拆分 然后再重新组合 具体的情况也得分析来看 如果节点数目是偶数个 那么正好平分然后将后一半的链表反转 之后就可以插入了如果节点数据是奇数个 那么前半部多一个 然后后半部反转之后进行插入 *//*链表的反转 */void Reverse(List*& list){List* tmp = NULL;List* cur = list;List* next = list->next;while(next != NULL){cur->next = tmp;tmp = cur;cur = next;next = next->next;} cur->next = tmp;list = cur;}void Reorder_list(List*& list){List* first = list;List* second;List* tmp_first,*tmp_second;int len = Len_list(first);int i;if(len%2 == 0){for(i=1;i<len/2;i++)first = first->next;}else{for(i=1;i<(len/2)+1;i++)first = first->next;} second = first->next;first->next = NULL;Reverse(second);first = list; // 开始进行融合 首先可以保证的是second链表的个数肯定不会比first链表的节点数目多while(second != NULL){tmp_first = first->next;tmp_second = second->next;first->next = second;second->next = tmp_first;second = tmp_second;first= tmp_first;} }int main() {int array[]={1,2,3,4,5,6,7,8,9,10,11,12};List* head;Init_List(head,array,sizeof(array)/sizeof(array[0])); Reorder_list(head);print_list(head);return 0;}
，让我们从自身的禁锢中放心地飞出去，重新审视自己，
