重新排序链表

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode * reorder(ListNode *phead)//链表的反转
{
　　if(phead==NULL || phead->next==NULL)
　　　　return phead;
　　ListNode *p=phead;
　　ListNode *q=p->next;
　　ListNode *s=q->next;
　　while(q)
　　{
　　q->next=p;
　　p=q;
　　q=s;
　　s=s->next;
　　}
　　phead->next=NULL;
　　phead=p;
　　return phead;
}
ListNode *getmid(ListNode *head)//取得链表的中点
{
　　if(head==NULL || head->next==NULL)
　　　　return head;
　　ListNode *p=head;
　　ListNode *q=head;
　　while(q&&q->next)
　　{
　　p=p->next;
　　q=q->next->next;
　　}
return p;
}
ListNode * mergeList(ListNode *l1,ListNode *l2)//合并链表
{
　　if(l1==NULL)
　　　　return l2;
　　if(l2==NULL)
　　　　return l1;
　　int count=1;
　　ListNode *head=new ListNode(0);
　　ListNode *p=head;
　　while(l1!=NULL && l2!=NULL)
　　{
　　if(count%2==1)
　　{
　　p->next=l1;
　　l1=l1->next;

　　}else
　　{
　　p->next=l2;
　　l2=l2->next;
　　}
　　count++;
　　p=p->next;
　　}
　　if(l1!=NULL)
　　　　p->next=l1;
　　if(l2!=NULL)
　　　　p->next=l2;
　　return head->next;
}

void reorderList(ListNode *head) {
　　if(head==NULL || head->next==NULL)
　　　　return;
　　ListNode *mid=getmid(head);
　　ListNode *phead=reorder(mid->next);
　　mid->next=NULL;
　　head=mergeList(head,phead);


}
};

重新排序链表

原文：http://www.cnblogs.com/ranranblog/p/5587166.html