[Leetcode] Reorder list 重排链表

Given a singly linked list L: L 0→L 1→…→L n-1→L n,
reorder it to: L 0→L n →L 1→L n-1→L 2→L n-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}.

反转以后的链表是，从左往右是，node₀->node_n->node₁->noden_n-1->.....，首先想到是将链表L按照这个规律重新赋值一遍，但题中说不能改变结点的值；然后想到将链表反转然后重新连接起来，如1->2->3->4，

按虚线那样走，形成1->4->2->3->3->2->4->1，若是结点的值都不相同，则遇到相同时，就可以断开形成，若是有相同，可先统计结点的个数，然后判断终止条件。这样就需要新建一个链表。所以想到将链表一分为二，反转后半段，然后重新连接起来，依旧是1->2->3->4，

这样思路就出来了，分三步走，第一步，将链表一分为二，用到快慢指针；第二步，反转第二部分，反转链表是很重要的根基；第三步，将两链表接起来。参考了JustDoIt的博客。

使用快慢指针将链表分成两段，采用这种方式会导致在链表结点个数为奇数的情况下，后半段的个数比前半段多一个。前半段一preSlow维结束，后半段一slow开始。所以在第三步将两子链表连接起来的时候，要注意判断反转以后以newBeg开始的后半段是否已经结束，没有，则连接上剩余部分即可。

针对反转链表，要认真的理解，关键是反转以后，要在新的链表结尾加上next=NULL。

 /**

  * Definition for singly-linked list.

  * struct ListNode {

  *     int val;

  *     ListNode *next;

  *     ListNode(int x) : val(x), next(NULL) {}

  * };

  */

 class Solution {

 public:

     void reorderList(ListNode *head)

     {

         if(head==NULL||head->next==NULL)

             return;

         //分成两段

         ListNode *preSlow=NULL;

         ListNode *slow=head,*fast=head;

         while(fast&&fast->next)

         {

             preSlow=slow;

             slow=slow->next;

             fast=fast->next->next;

         }

         preSlow->next=NULL; //前半段

         //反转后半段

         ListNode *newBeg=slow;

         ListNode *last=newBeg->next;

         while(last)

         {

             ListNode *temp=last->next;

             last->next=newBeg;

             newBeg=last;

             last=temp;

         }

         slow->next=NULL;

         //合并

         fast=head;

         preSlow=NULL;

         while(fast) //注：以前半段为条件

         {

             ListNode *tem=newBeg->next;

             newBeg->next=fast->next;

             fast->next=newBeg;

             fast=newBeg->next;

             preSlow=newBeg;

             newBeg=tem;

         }

         if(newBeg !=NULL)   //因节点个数为奇数时，后段比前段多一个，所以最后要判断

             preSlow->next=newBeg;

     }

 };

巴特西

[Leetcode] Reorder list 重排链表

最新文章

热门文章