题解 | #单链表的排序#
单链表的排序
http://www.nowcoder.com/practice/f23604257af94d939848729b1a5cda08
归并排序的样板代码,主要是合并两个链表的部分,以及要注意在归并前需要断开链表,否则会死循环。
#include<iostream> #include<vector> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; class Solution { public: ListNode* mergeSort(ListNode* head) { if(head==NULL || head->next==NULL) return head; ListNode *fast = head, *slow = head, *pre; while(fast && fast->next) { pre = slow; fast = fast->next->next; slow = slow->next; } pre->next = NULL; ListNode* left = mergeSort(head); ListNode* right = mergeSort(slow); ListNode* dummy = new ListNode(0); ListNode* p = dummy; while(left || right) { if(left == NULL || (right && right->val < left->val)) { p->next = right; right = right->next; } else{ p->next = left; left = left->next; } p = p->next; } return dummy->next; } ListNode* sortInList(ListNode* head) { return mergeSort(head); } };