Sort a linked list in O(n log n) time using constant space complexity.
单向链表排序O(nlogn),Mergesort可以实现。
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 class Solution { 10 public: 11 ListNode *sortList(ListNode *head) { 12 if (head == nullptr || head->next == nullptr) { 13 return head; 14 } 15 //快慢指针找中间节点 16 ListNode *fast = head, *slow = head; 17 while (fast->next != nullptr && fast->next->next != nullptr) { 18 fast = fast->next->next; 19 slow = slow->next; 20 } 21 22 fast = slow->next; 23 slow->next = nullptr; 24 ListNode *l1 = sortList(head); 25 ListNode *l2 = sortList(fast); 26 return mergeTwoLists(l1, l2); 27 } 28 29 private: 30 // Merge Two Sorted Lists 31 ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) { 32 ListNode dummy(-1); 33 for (ListNode* p = &dummy; l1 != nullptr || l2 != nullptr; p = p->next) { 34 int val1 = l1 == nullptr ? INT_MAX : l1->val; 35 int val2 = l2 == nullptr ? INT_MAX : l2->val; 36 if (val1 <= val2) { 37 p->next = l1; 38 l1 = l1->next; 39 } else { 40 p->next = l2; 41 l2 = l2->next; 42 } 43 } 44 return dummy.next; 45 } 46 };
【Leetcode】Sort List,布布扣,bubuko.com
原文:http://www.cnblogs.com/dengeven/p/3778719.html