链表排序的归并解法

链表排序的归并解法

我才用归并排序的方式对链表进行排序。

总所周知归并排序分为两部分，第一部分为用分治法对数据进行切割，第二部分为将分开的两部分，按大小进行合并。

我们来进行第一步，在常规的数组归并的第一个部分时，我们传递的marge中的值一班为，marge(数组,begin,end)。但在链表中那个end很难用一个值来表示。所以我们用一个快指针和一个慢指针实现第一部分。

Pnode fast,slow;
fast=slow=head;
while(fast->next!=NULL&&fast->next->next!=NULL)
{
	fast=fast->next->next;
	slow=slow->next;
}
fast=slow;
slow=slow->next;
fast->next=NULL;

如上图，快指针fast一次动两个，慢指针一次动一个，当fast不能动时，slow就在中间位置了，虽然不一定时正中间，但是不影响。

当fast不能动了时，slow就有大用处了，当循环结束时，fast的用处已经没了，我们就把fast重利用一次，我们把slow节点和slow->next节点断开，然后整个循环就变成了head到slow和slow->next 到NULL了， 所以我们用fast将slow的next赋值为NULL，slow往后面移动一次。

我们会分开后，就应该写递归切割的过程了，这个非常的关键。

fast = Sort(head);
slow = Sort(slow);
return Solution(fast,slow);

如上图，我们假设fast为前一段，slow为后一段，我们把递归回来的已经排序好了的链表放在fast前段和slow后段里面。

然后是Solution的过程。

Pnode Solution(Pnode head1,Pnode head2)
{
	if(head1==NULL) return head2;
	if(head2==NULL) return head1;
	Pnode ans;
	if(head1->datadata){ans=head1;head1=head1->next;}
	else {ans=head2;head2=head2->next;}
	Pnode p=ans;
	while(head2!=NULL&&head1!=NULL)
	{
		if(head1->datadata){p->next=head1;head1=head1->next;}
		else {p->next=head2;head2=head2->next;}
	p=p->next;
	}
	if(head1==NULL) p->next=head2;
	else if(head2==NULL) p->next=head1;
	return ans;
}

 与数组的归并差不多，就是要注意头指针为空的情况，因为我们都是地址传递，所以不需要用一个新的链表存储，只要用一个ans 的头指针即可保存当前排序的结果。

完整代码如下：

#include
#include
typedef struct list{
	int data;
	struct list * next;
	struct list * pre;
}*Pnode,Node;
#define NEW (Pnode)malloc(sizeof(Node))
Pnode build(int num)
{
	Pnode head,p1,p2;
	head=p1=NULL;
	for(int i=0;idata=data;p1->next=NULL;}
		else {p2=NEW;p2->data=data;p1->next=p2;p2->pre=p1;p1=p2;p1->next=NULL;}
	}
	p1->next=NULL;
	return head;
}
Pnode Solution(Pnode head1,Pnode head2)
{
	if(head1==NULL) return head2;
	if(head2==NULL) return head1;
	Pnode ans;
	if(head1->datadata){ans=head1;head1=head1->next;}
	else {ans=head2;head2=head2->next;}
	Pnode p=ans;
	while(head2!=NULL&&head1!=NULL)
	{
		if(head1->datadata){p->next=head1;head1=head1->next;}
		else {p->next=head2;head2=head2->next;}
	p=p->next;
	}
	if(head1==NULL) p->next=head2;
	else if(head2==NULL) p->next=head1;
	return ans;
}
Pnode Sort(Pnode head)
{
if(head==NULL||head->next==NULL) return head;
Pnode fast,slow;
fast=slow=head;
while(fast->next!=NULL&&fast->next->next!=NULL)
{
	fast=fast->next->next;
	slow=slow->next;
}
fast=slow;
slow=slow->next;
fast->next=NULL;
fast = Sort(head);
slow = Sort(slow);
return Solution(fast,slow);
}
main()
{
	int m;
	scanf("%d",&m);
	getchar();
	Pnode head=build(m);
	Pnode ans=Sort(head);
	while(ans!=NULL)
	{
		printf("%d ",ans->data);
		ans=ans->next;
	}
}