给定一个单链表 L：L0→L1→…→Ln-1→Ln ， 将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1:
给定链表 1->2->3->4, 重新排列为 1->4->2->3.
示例 2:
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
具体看注释：
我还想说的一件事是，逆置，每个结点的内存地址没变，只是内存间相互指的顺序变，但那又什么关系呢？没关系。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: void reorderList(ListNode* head) { //链表首先考虑为空或者只有一个结点的情况。 if(head==NULL||head->next==NULL) return ; //那就逆置一半 //先快慢指针找到中点 ListNode *slow=head; ListNode *fast=head; ListNode *pre; while(fast&&fast->next) { pre=slow; slow=slow->next; fast=fast->next->next; } //奇数的话经过上面，slow正好在中点上，偶数的话没有中点，就在靠后一个即n/2+1处 /*对的，但不规范。 pre->next=reverse(slow);//逆转slow及以后。 ListNode *last=pre->next;//这个原来的slow的位置变成Ln pre->next=NULL;//断开前后 cout<<last->val<<endl; //取到后半部分之后就可以从头开始插入啦 ListNode *p=head; //验证后半部分 // while(last) // { // cout<<last->val<<" "; // last=last->next; //} //验证前半部分 //while(p) //{ // cout<<p->val<<" "; // p=p->next; //} while(p->next) { //pre2=p; ListNode *lastnext=last->next; last->next=p->next; p->next=last; p=last->next; last=lastnext; } p->next=last;*/ //又对又规范，没有带着中点逆转，而是指逆转了终点之后的部分。我分析了，slow->next最多为NULL，经过上面的判断，不会有slow为NULL出现slow->next空指针的情况，所以对的。 cout<<slow->val<<endl; slow->next=reverse(slow->next);//只逆转slow以后的部分。 ListNode *last=slow->next; slow->next=NULL;//断开前后！！！！！ //cout<<last->val<<endl; //取到后半部分之后就可以从头开始插入啦 ListNode *p=head; //本来的话这样分3步合并两个链表是没有问题的。 //但是这个题奇数的时候因为我们前面是从中点就开始反转，把中点翻转到last那边了，所以不行，所以用上面那个，p的后面到了null，接上没到null的last.而之所以是p->next而不是p，是为了好接，到p=NULL的时候就晚了，就需要再存一个pre才能接上了。 while(p&&last) { ListNode *lastnext=last->next; ListNode *pnext=p->next; p->next=last; p=pnext; last->next=p; last=lastnext; } /*下面典型错误（当然注释没错），想直接逆置整个表。错在哪呢？这样的话原来整个表就没了。 //实际上就是把Ln和Ln-1依次插入到L0和L1、L1和L2....之间。 ListNode *t=head; ListNode *rhead=reverse(t); ListNode *rp=rhead; ListNode *p=head; //验证逆置是否成功，成功。 //因为是原地逆置，所以是不是原来的已经不在了。是的！所以就不可行。 //while(rp) //{ // cout<<rp->val<<endl; // rp=rp->next; //} //验证原来的链表是不是变了。 //while(p) //{ // cout<<p->val<<endl; // p=p->next; //} //合并两个链表。 while(p)//我觉得应该是p先到。 { ListNode *pnext=p->next; ListNode *rpnext=rp->next; p->next=rp; rp->next=pnext; rp=rpnext; p=pnext; } */ } ListNode *reverse(ListNode *head) { ListNode *pre=NULL; ListNode *cur=head; ListNode *next; while(cur) { next=cur->next; cur->next=pre; pre=cur; cur=next; } return pre; } };
