首先給出快排解法：
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); }};快排使用二級(jí)指針很方便，所以盡量用二級(jí)指針。
下面是歸并，先給一個(gè)使用dummy的版本：
class Solution {public: ListNode *sortList(ListNode *head) { if(head == NULL || head->next == NULL) return head; ListNode* slow = head; //fast必須從next開始，因?yàn)槭菤w并。而且這不是求鏈表入環(huán)點(diǎn)，不必do-while那么嚴(yán)格的要求 //如果不是head->next，那么如果鏈表為[2,1]兩個(gè)元素， //會(huì)陷入死循環(huán)，每次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) //注意不要忘了后續(xù)鏈表 tmp->next = node1; else tmp->next = node2; return dummy->next; }};如果不使用dummy，合并兩個(gè)排序鏈表有傳統(tǒng)的套路，就是下面的遞歸方法：
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; }一日后更新：哈哈，經(jīng)過這兩天的刷題，又掌握了一種新的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; }};新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
