单链表排序(插入与归并)

分类：数据结构与算法

struct ListNode {int val;ListNode *next;ListNode(int x) : val(x), next(NULL) {} };/* * 单链表的插入排序, 插入排序是一种稳定排序 */class Solution7 {public:ListNode* insertionSortList(ListNode* head) {if(head == NULL || head->next == NULL)return head;ListNode *prev = head, *next = head->next;ListNode *tmp;while(next != NULL){if(prev->val <= next->val){//注意保持稳定性prev = next;next = next->next;}else{prev->next = next->next;if(head->val > next->val){//保持稳定性next->next = head;head = next;}else{tmp = head;while(tmp->next->val <= next->val){//保持稳定性tmp = tmp->next;}next->next = tmp->next;tmp->next = next;}next = prev->next;}}return head;}};/* * 单链表的归并排序, O(nlgn) */class Solution8 {public:ListNode* sortList(ListNode* head) {if(head == NULL || head->next == NULL) return head;//1 快慢指针进行链表分割ListNode *fast=head, *slow = head, *prev=NULL;while(fast && fast->next){prev = slow;slow = slow->next;fast = fast->next->next;}prev->next = NULL;//2 二分ListNode *left_head = sortList(head);ListNode *right_head = sortList(slow);//3 合并ListNode dummy(-1);prev = &dummy;while(left_head && right_head){if(left_head->val < right_head->val){prev->next = left_head;left_head = left_head->next;prev = prev->next;}else{prev->next = right_head;right_head = right_head->next;prev = prev->next;}//剩余部分合并while(left_head != NULL){prev->next = left_head;left_head = left_head->next;prev = prev->next;}while(right_head != NULL){prev->next = right_head;right_head = right_head->next;prev = prev->next;}return dummy.next;}};

上一篇解剖Nginx·自动脚本篇（1）解析配置选项脚本 auto/options下一篇单链表翻转的几种写法

顶1踩0

为何是一个人？也有善意的提醒：

相关文章：

你感兴趣的文章：

标签云：