leetcode做题笔记148. 排序链表

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

思路一：归并排序

c语言解法

struct ListNode* merge(struct ListNode* head1, struct ListNode* head2) {struct ListNode* dummyHead = malloc(sizeof(struct ListNode));dummyHead->val = 0;struct ListNode *temp = dummyHead, *temp1 = head1, *temp2 = head2;while (temp1 != NULL && temp2 != NULL) {if (temp1->val <= temp2->val) {temp->next = temp1;temp1 = temp1->next;} else {temp->next = temp2;temp2 = temp2->next;}temp = temp->next;}if (temp1 != NULL) {temp->next = temp1;} else if (temp2 != NULL) {temp->next = temp2;}return dummyHead->next;
}struct ListNode* toSortList(struct ListNode* head, struct ListNode* tail) {if (head == NULL) {return head;}if (head->next == tail) {head->next = NULL;return head;}struct ListNode *slow = head, *fast = head;while (fast != tail) {slow = slow->next;fast = fast->next;if (fast != tail) {fast = fast->next;}}struct ListNode* mid = slow;return merge(toSortList(head, mid), toSortList(mid, tail));
}struct ListNode* sortList(struct ListNode* head) {return toSortList(head, NULL);
}

分析：

本题要将链表排序，由于链表的特性，无法直接从中间进行修改，所以利用快慢指针将链表分为两部分，对两个子链表进行排序，通过递归不断将链表分为两部分，直到无法分为止，最后合并所有的链表，得到排序后的链表

思路二：转换为数组后进行排序再转换为链表

c语言解法(此解法有取巧的成分，但时间复杂度上优于思路一，故列出）

int cmp(const int* a,const int* b)
{return *(int*)a - *(int*)b;
}struct ListNode* sortList(struct ListNode* head)
{int A[50000]={0};int i = 0;struct ListNode* tmp = head;for(i=0; tmp != NULL; i++){A[i] = tmp->val;tmp = tmp->next;}qsort(A,i,sizeof(int),cmp);tmp = head;for(i=0; tmp != NULL;i++){tmp->val = A[i];tmp = tmp->next;}return head;
}

分析：

第二种思路则是将原链表转换为数组后进行排序再转换为链表，此解法更加直观，同时数组排序更加熟悉，此处利用快速排序排序数组，最后返回排序好的链表即可解决

总结：

本题考察对链表的排序操作，利用归并排序即可解决，也可转换为数组后利用数组的方法解决。