leetcode 148. 排序链表 中等

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

示例 1：

输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：

输入：head = []
输出：[]

分析：

方法一：将链表的所有元素存放在数组中进行排序，再将排好序的数值依次放到链表里。

//方法一
/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
int cmp(const void *a,const void *b)
{int *aa=(int*)a;int *bb=(int*)b;return *aa-*bb;
}struct ListNode* sortList(struct ListNode* head) {if(head==NULL)return NULL;struct ListNode *p=head;int num[50010]={0},t=0;while(p!=NULL)num[t++]=p->val,p=p->next;qsort(num,t,sizeof(int),cmp);p=head;int l=0;while(p!=NULL)p->val=num[l++],p=p->next;return head;
}

方法二：快速排序。

找到链表中的最大值和最小值，以它们的平均数mid作为分界值，小于等于mid的放到链表h1，大于mid的放到链表h2，之后再把h2挂在h1的后面即可。

//方法二 快速排序
/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/struct ListNode* sortList(struct ListNode* head) {if(head==NULL)return NULL;if(head->next==NULL)return head;struct ListNode *prehead=(struct ListNode*)malloc(sizeof(struct ListNode));prehead->next=head;struct ListNode *h1=(struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode *h2=(struct ListNode*)malloc(sizeof(struct ListNode));h1->next=h2->next=NULL;int l=head->val,r=head->val;while(head->next!=NULL){head=head->next;l=fmin(l,head->val);r=fmax(r,head->val);}if(l==r){struct ListNode *p=prehead->next;free(prehead);free(h1);free(h2);return  p;     }int mid=(l+r)>>1;head=prehead->next;struct ListNode *p=head;while(head!=NULL){p=head;head=head->next;if(p->val<=mid)p->next=h1->next,h1->next=p;else p->next=h2->next,h2->next=p;}h1->next=sortList(h1->next);h2->next=sortList(h2->next);p=h1;while(p->next!=NULL)p=p->next;p->next=h2->next;struct ListNode *ans=h1->next;free(prehead);free(h1);free(h2);return ans;
}

方法三：自顶向下归并排序。

• 找到链表的中点，以中点为分界，将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针的做法，快指针每次移动 2 步，慢指针每次移动 1 步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点。
• 对两个子链表分别排序。
• 将两个排序后的子链表合并，得到完整的排序后的链表。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/struct ListNode* sortList(struct ListNode* head) {if(head==NULL)return NULL;if(head->next==NULL)return head;struct ListNode *prehead=(struct ListNode*)malloc(sizeof(struct ListNode));prehead->next=head;struct ListNode *fast,*low;fast=low=prehead;while(fast->next!=NULL){low=low->next;fast=fast->next;if(fast->next!=NULL)fast=fast->next;}if(fast==low){free(prehead);return fast;}struct ListNode *h1=(struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode *h2=(struct ListNode*)malloc(sizeof(struct ListNode));h1->next=head;h2->next=low->next;low->next=NULL;h1->next=sortList(head);h2->next=sortList(h2->next);struct ListNode *h=(struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode *p,*q,*r;p=h1->next,q=h2->next,r=h;while(p!=NULL||q!=NULL){if(p==NULL&&q!=NULL)r->next=q,q=q->next;else if(p!=NULL&&q==NULL)r->next=p,p=p->next;else if(p->val<q->val)r->next=p,p=p->next;else r->next=q,q=q->next;r=r->next;}//r->next=NULL;p=h->next;free(h1);free(h2);free(h);return p;
}

 

方法四：自底向上归并排序

具体做法如下。

• 用 subLength 表示每次需要排序的子链表的长度，初始时 subLength=1。
• 每次将链表拆分成若干个长度为 subLength 的子链表（最后一个子链表的长度可以小于 subLength），按照每两个子链表一组进行合并，合并后即可得到若干个长度为 subLength×2 的有序子链表（最后一个子链表的长度可以小于 subLength×2）。
• 将 subLength 的值加倍，重复第 2 步，对更长的有序子链表进行合并操作，直到有序子链表的长度大于或等于 length，整个链表排序完毕。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
//方法四 这里我把调试的部分也留下了
struct ListNode* sortList(struct ListNode* head) {if(head==NULL)return NULL;if(head->next==NULL)return head;struct ListNode *prehead=(struct ListNode*)malloc(sizeof(struct ListNode));prehead->next=head;int l=0,t=0;struct ListNode *p=head,*q=prehead;while(p!=NULL)l++,p=p->next;p=prehead->next;for(int i=1;i<l;i=fmin(i*2,l)){p=prehead->next;t=0;struct ListNode *index;while(p!=NULL){int l1=0,l2=0;struct ListNode *p1,*q1,*p2,*q2;p1=p;while(p!=NULL&&l1<i)l1++,q1=p,p=p->next;q1->next=NULL;if(p==NULL)break;p2=p;while(p!=NULL&&l2<i)l2++,q2=p,p=p->next;q2->next=NULL;
/*printf("i=%d l=%d\n",i,l);struct ListNode *test=p1;printf("p1=");while(test!=NULL)printf("%d ",test->val),test=test->next;printf("\n");test=p2;printf("p2=",i);while(test!=NULL)printf("%d ",test->val),test=test->next;printf("\n");
*/struct ListNode *h=(struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode *r=h;while(p1!=NULL||p2!=NULL){if(p1==NULL&&p2!=NULL)r->next=p2,p2=p2->next;else if(p1!=NULL&&p2==NULL)r->next=p1,p1=p1->next;else if(p1->val<p2->val)r->next=p1,p1=p1->next;else r->next=p2,p2=p2->next;r=r->next;}if(t==0)prehead->next=h->next,t++,index=r;else index->next=h->next,index=r;;r->next=p;
/*test=h->next;printf("test=");while(test!=NULL)printf("%d ",test->val),test=test->next;printf("\n");
*/free(h);
/*printf("r=%d\n",r->val);test=p;printf("p=",i);while(test!=NULL)printf("%d ",test->val),test=test->next;printf("\n");test=prehead->next;printf("prehead=",i);while(test!=NULL)printf("%d ",test->val),test=test->next;printf("\n");
*/}}q=prehead->next;free(prehead);return q;
}

 

方法三、方法四来源：

作者：力扣官方题解
链接：https://leetcode.cn/problems/sort-list/solutions/492301/pai-xu-lian-biao-by-leetcode-solution/