基础数据结构——需要重新排列链表

重新排列链表的思路本文将给出C++实现的三种方法数组模拟双向队列模拟直接拆分链表的方法将链表放入数组，以及然后用双指针的方法，一个接一个，遍历数组，构造链表。代码如下：(cur);cur=cur->next;}cur=head;inti=1;intj=vec.size()-1;//ij为前后双指针intcount=0;//计数，偶数往后走，奇数取while(i<=j){if(count%2==0){cur->next=vec[j];j--;}else{cur->next=vec[i];i++;}cur=cur->next;count++;}cur->next=nullptr;//注意最后}};方法二将链表放入双向队列，然后通过双向队列将数据一个一个弹出，构造一个新的链表。这种方法比操作数组更容易。它不使用双指针来模拟一个接一个。;while(cur->next!=nullptr){que.push_back(cur->next);cur=cur->next;}cur=head;intcount=0;//计数，偶数到后面，奇数数字取前面ListNode*node;while(que.size()){if(count%2==0){node=que.back();que.pop_back();}else{node=que.front();que.pop_front();}count++;cur->next=node;cur=cur->next;}cur->next=nullptr;//注意结尾}};方法3将链表分成两个链表，然后将第二个链表进行反转，然后将两个链表拼接成一个新的链表。如图：这种方法比较难。平均切割链表看起来很简单。写真正代码的时候有很多细节。同时，在两个链表之后组装新的链表时，还有一些需要注意的细节！代码如下：classSolution{private://反向链表ListNode*reverseList(ListNode*head){ListNode*temp;//保存cur的下一个节点ListNode*cur=head;ListNode*pre=NULL;while(cur){temp=cur->next;//保存cur的下一个节点，因为下一步要改变cur->nextcur->next=pre;//翻转操作//更新pre和cur指针pre=cur;cur=temp;}returnpre;}public:voidreorderList(ListNode*head){if(head==nullptr)return;//使用快慢指针的方法将链表分成两个等长的链表head1和head2//如果总链表长度为奇数，则head1相对于head2多一个节点ListNode*fast=head;ListNode*slow=head;while(fast&&fast->next&&fast->next->next){fast=fast->next->next;slow=slow->next;}ListNode*head1=head;ListNode*head2;head2=slow->next;slow->next=nullptr;//反转head2head2=reverseList(head2);//交替head1和head2生成新的链表headListNode*cur1=head1;ListNode*cur2=head2;ListNode*cur=head;cur1=cur1->next;intcount=0;//偶数取head2的元素，奇数取head1的元素while(cur1&&cur2){if(count%2==0){cur->next=cur2;cur2=cur2->next;}else{cur->next=cur1;cur1=cur1->next;}count++;cur=cur->next;}if(cur2!=nullptr){//处理结束cur->next=cur2;}if(cur1!=nullptr){当前->下一个=cur1；}}}；其他语言版本Java//方法3publicclassReorderList{publicvoidreorderList(ListNodehead){ListNodefast=head,slow=head;//求中点while(fast.next!=null&&fast.next.next!=null){slow=slow.next;fast=fast.next.next;}//right为右半部分12345is451234is34ListNoderight=slow.next;//将左右部分断开slow.next=null;//反转右半部分rightis反转后右边部分的起点right=reverseList(right);//左边部分的起点ListNodeleft=head;//来回连接左右部分//左边部分的节点在这里数量必须大于等于右边部分的节点数，所以只能判断右边while(right!=null){ListNodecurLeft=left.next;left.next=right;left=curLeft;ListNodecurRight=right.next;right.next=left;right=curRight;}}publicListNodereverseList(ListNodehead){ListNodeheadNode=newListNode(0);ListNodecur=head;ListNodenext=null;while(cur!=null){next=cur.next;Cur.next=headNode.next;headNode.next=cur;cur=next;}returnheadNode.next;}}//Java实现方法一，使用数组存储节点classSolution{publicvoidreorderList(ListNodehead){//双指针的实践ListNodecur=head;//ArrayList底层是数组，可以通过下标随机访问Listlist=newArrayList<>();while(cur!=null){list.add(cur);cur=cur.next;}cur=head;//返回头部intl=1,r=list.size()-1;//注意左边从1开始intcount=0;while(l<=r){if(count%2==0){//偶数cur.next=list.get(r);r--;}else{//奇数cur.next=list.get(l);l++;}//每指针需要移动cur=cur.next;count++;}//注意结束一波cur.next=null;}}//方法二：使用双端队列，简化了对数组的操作，以及代码比前者更简洁（避免了一些边界条件）classSolution{publicvoidreorderList(ListNodehead){//使用双端队列的方法求解Dequede=newLinkedList<>();//这里是head的下一个节点，head不需要重新进入Teamup，避免重复ListNodecur=head.next;while(cur!=null){de.offer(cur);cur=cur.next;}cur=head;//回到头部intcount=0;while(!de.isEmpty()){if(count%2==0){//偶数，取出队列右端cur的值.next=de.pollLast();}else{//奇数，取出左队头的cur.next=de.poll();}cur=cur.next;count++;}cur.next=null;}}Python的值#method双向队列类解决方案：defreorderList(self,head:ListNode)->None:"""不要返回任何东西，修改headin-placeinstead."""d=collections.deque()tmp=headwhilemp.next:#链表除了第一个元素加入双向队列d.append(tmp.next)tmp=tmp.nextttmp=headwhilen(d):#加入链表在tmp.next=d之前一个接一个。pop()tmp=tmp.nextiflen(d):tmp.next=d.popleft()tmp=tmp.nextttmp.next=None#Tailempty#方法3反向链表类解决方案：defreorderList(self,head:ListNode)->None:ifhead==Noneorhead.next==None:returnTrueslow,fast=head,headwhilefastandfast.next:slow=slow.nextfast=fast.next.nextright=slow.next#Splittherighthalfslow.next=None#Cutoffright=self.reverseList(right)#反转右半部分left=head#左半部分必须比右半部分长，所以可以判断右半部分whileright:curLeft=left.nextleft.next=rightleft=curLeftcurRight=right.nextright.next=leftright=curRightdefreverseList(self,head:ListNode)->ListNode:cur=headpre=Nonewhile(cur!=None):temp=cur.next#保存cur的下一个节点cur.next=pre#反向pre=curcur=tempreturnpre