148. Sort List（快排、归并）

2019-11-08 01:41:49

字体：大中小

来源：转载

供稿：网友

Sort a linked list in O(n log n) time using constant space complexity.

首先给出快排解法：

class Solution {public: ListNode *sortList(ListNode *head) { if(head == NULL) return NULL; quick_sort(&head, NULL); return head; } void quick_sort(ListNode** head, ListNode* end){ if(*head == end) return ; ListNode *right = NULL; ListNode *pivot = *head; ListNode **left_walk = head; ListNode **right_walk = &right; for(ListNode* old=(*head)->next; old!=end; old=old->next){ if(old->val < pivot->val){ *left_walk = old; left_walk = &(old->next); } else{ *right_walk = old; right_walk = &(old->next); } } *right_walk = end; *left_walk = pivot; pivot->next =right; quick_sort(&(pivot->next), end); quick_sort(head, pivot); }};

快排使用二级指针很方便，所以尽量用二级指针。

下面是归并，先给一个使用dummy的版本：

class Solution {public: ListNode *sortList(ListNode *head) { if(head == NULL || head->next == NULL) return head; ListNode* slow = head; //fast必须从next开始，因为是归并。而且这不是求链表入环点，不必do-while那么严格的要求 //如果不是head->next，那么如果链表为[2,1]两个元素， //会陷入死循环，每次fast最终传入merge都为NULL，链表长度没变 ListNode* fast = head->next; while(fast != NULL && fast->next != NULL){ slow = slow->next; fast = fast->next->next; } fast = slow->next; slow->next = NULL; return merge(sortList(head), sortList(fast)); } ListNode* merge(ListNode* node1, ListNode* node2){ ListNode* dummy = new ListNode(-1); ListNode* tmp = dummy; while(node1 != NULL && node2 != NULL){ if(node1->val < node2->val){ tmp->next = node1; node1 = node1->next; } else{ tmp->next = node2; node2 = node2->next; } tmp = tmp->next; } if(node1 != NULL) //注意不要忘了后续链表 tmp->next = node1; else tmp->next = node2; return dummy->next; }};

如果不使用dummy，合并两个排序链表有传统的套路，就是下面的递归方法：

ListNode* merge(ListNode* node1, ListNode* node2){ if(node1 == NULL) return node2; else if(node2 == NULL) return node1; ListNode* res = NULL; if(node1->val < node2->val){ res = node1; res->next = merge(node1->next, node2); } else{ res = node2; res->next = merge(node1, node2->next); } return res; }

一日后更新：哈哈，经过这两天的刷题，又掌握了一种新的merge方法：

class Solution {public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode* head = NULL; ListNode** pp = &head; while(l1 != NULL && l2 != NULL){ if(l1->val < l2->val){ *pp = l1; pp = &(l1->next); l1 = l1->next; } else{ *pp = l2; pp = &(l2->next); l2 = l2->next; } } if(l1 != NULL) *pp = l1; else *pp = l2; return head; }};

上一篇：Flying to the Mars hdu1800 trie

下一篇：HDU 1114 Piggy-Bank(完全背包)

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注