Leetcode 147. 对链表进行插入排序 Leetcode 148. 排序链表

本文主要是介绍Leetcode 147. 对链表进行插入排序 Leetcode 148. 排序链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://leetcode-cn.com/problems/insertion-sort-list/
https://leetcode-cn.com/problems/sort-list/

插入排序-初版

复杂度如插入排序，最坏可能为O(n^2)

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/struct ListNode* insertionSortList(struct ListNode* head){if ( head == NULL || head->next == NULL ) {return head;}struct ListNode *res = (struct ListNode *) calloc (sizeof(struct ListNode), 1), //虚拟前驱节点*prev = res, //前驱节点，默认为 虚拟前驱节点*tmp = NULL; //临时节点while ( head ) {for ( prev = res; prev->next && prev->next->val < head->val; prev = prev->next ) { //从前往后寻找插入排序的位置}tmp = prev->next; //临时存储后续元素的指针prev->next = head; //把当前待排序元素插入后边head = head->next; //指向下个待排序节点prev->next->next = tmp; //链接剩余的元素}return res->next;
}

插入排序法-改进版

例如，给定链表：1 -> 5 -> 4 -> 2 -> 7 -> 6
利用上边的排序算法进行，比如说对7进行排序。
此时
已排序链表：1 -> 2 -> 4 -> 5
待排序链表：7 -> 6

则此时还需要把已排序链表从头到尾的遍历一遍，效率有点不太高，要是可以直接记录最后一个已排序的节点，可以优先比较，如果比最后一个节点大，直接放到“已排序链表”末尾，则可以节省一次从前到后的对“已排序链表”的遍历。但是全部都是逆序，即使记录末尾节点，也无法优化。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/struct ListNode* insertionSortList(struct ListNode* head){if ( head == NULL || head->next == NULL ) {return head;}struct ListNode *res = (struct ListNode *) calloc (sizeof(struct ListNode), 1), //虚拟前驱节点*prev = res, //前驱节点，默认为 虚拟前驱节点*tmp = NULL, //临时节点*lastSorted = NULL; //最后一个节点while ( head ) {if ( lastSorted && lastSorted->val <= head->val) {lastSorted->next = head; //把当前待排序元素插入后边head = head->next; //指向下个待排序节点lastSorted = lastSorted->next; //指向末尾节点lastSorted->next = NULL; //把末尾节点断开} else {for ( prev = res; prev->next && prev->next->val < head->val; prev = prev->next ) { //从前往后寻找插入排序的位置}tmp = prev->next; //临时存储后续元素的指针prev->next = head; //把当前待排序元素插入后边head = head->next; //指向下个待排序节点prev->next->next = tmp; //链接剩余的元素if ( tmp == NULL ) { //记录末尾元素lastSorted = prev->next;}}}return res->next;
}

归并排序

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/struct ListNode* merge(struct ListNode* l1, struct ListNode* l2) {struct ListNode * head = (struct ListNode*) calloc(sizeof(struct ListNode), 1), *prev = head, *curr;while (l1 && l2) {if (l1->val < l2->val) {curr = l1;l1 = l1->next;} else {curr = l2;l2 = l2->next;}prev->next = curr;prev = curr;}prev->next = l1 ? l1 : l2;return head->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);
}

选择排序-链表排序

数组排序

void swap(int *a,int *b) {int temp = *a;*a = *b;*b = temp;
}void selection_sort(int arr[], int len) {int i,j, min;for (i = 0; i < len-1; i++) {for (min = i, j = i+1; j < len; j++) {    //遍历未排序的元素if (arr[j] < arr[min]) {   //找到最小值min = j;    //记录最小值}}       swap(&arr[min], &arr[i]);    //做交換}
}

模仿数组的链表选择排序

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/struct ListNode* sortList(struct ListNode* head){if ( head == NULL || head->next == NULL ) {return head;}struct ListNode *res = (struct ListNode *) calloc (sizeof(struct ListNode), 1), *tmp;res->next = head; //初始化for ( struct ListNode *i = res; i->next != NULL; i = i->next ) {struct ListNode *min = i;for ( struct ListNode *j = i->next; j->next != NULL; j = j->next ) { //遍历未排序的节点// printf("i=%d, j=%d, min=%d\n", i->next->val, j->next->val, min->next->val);if ( j->next->val < min->next->val ) { //找到目前最小值节点min = j; //记录最小值的节点指针}}if ( min != i ) { //节点做交换if ( i->next == min ) { //相临节点交换min = min->next;tmp = min->next;min->next = i->next;i->next = min;min->next->next = tmp;} else {//交换min与i节点的后继tmp = min->next->next;min->next->next = i->next->next;i->next->next = tmp;//交换min与i节点的前驱tmp = min->next;min->next = i->next;i->next = tmp;}}}return res->next;
}