Problem
Sort a linked list in O(n log n) time using constant space complexity.
Example 1:
Input: 4->2->1->3 Output: 1->2->3->4
Example 2:
Input: -1->5->3->4->0 Output: -1->0->3->4->5
Solution: Merge Sort
Top-down (recursion)
Time complexity: O(nlogn)
Space complexity: O(logn)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
// Author: Huahua // Running time: 32 ms /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* sortList(ListNode* head) { // 0 or 1 element, we are done. if (!head || !head->next) return head; ListNode* slow = head; ListNode* fast = head->next; while (fast && fast->next) { fast = fast->next->next; slow = slow->next; } ListNode* mid = slow->next; slow->next = nullptr; // Break the list. return merge(sortList(head), sortList(mid)); } private: ListNode* merge(ListNode* l1, ListNode* l2) { ListNode dummy(0); ListNode* tail = &dummy; while (l1 && l2) { if (l1->val > l2->val) swap(l1, l2); tail->next = l1; l1 = l1->next; tail = tail->next; } tail->next = l1 ? l1 : l2; return dummy.next; } }; |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
// Author: Huahua // Running time: 6 ms class Solution { public ListNode sortList(ListNode head) { if (head == null || head.next == null) return head; ListNode slow = head; ListNode fast = head.next; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; } ListNode mid = slow.next; slow.next = null; return merge(sortList(head), sortList(mid)); } private ListNode merge(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0); ListNode tail = dummy; while (l1 != null && l2 != null) { if (l1.val > l2.val) { ListNode tmp = l1; l1 = l2; l2 = tmp; } tail.next = l1; l1 = l1.next; tail = tail.next; } tail.next = (l1 != null) ? l1 : l2; return dummy.next; } } |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
# Author: Huahua, 232 ms class Solution: def sortList(self, head): def merge(l1, l2): dummy = ListNode(0) tail = dummy while l1 and l2: if l1.val > l2.val: l1, l2 = l2, l1 tail.next = l1 l1 = l1.next tail = tail.next tail.next = l1 if l1 else l2 return dummy.next if not head or not head.next: return head slow = head fast = head.next while fast and fast.next: fast = fast.next.next slow = slow.next mid = slow.next slow.next = None return merge(self.sortList(head), self.sortList(mid)) |
bottom up
Time complexity: O(nlogn)
Space complexity: O(1)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
// Author: Huahua // Running time: 32 ms class Solution { public: ListNode* sortList(ListNode* head) { // 0 or 1 element, we are done. if (!head || !head->next) return head; int len = 1; ListNode* cur = head; while (cur = cur->next) ++len; ListNode dummy(0); dummy.next = head; ListNode* l; ListNode* r; ListNode* tail; for (int n = 1; n < len; n <<= 1) { cur = dummy.next; // partial sorted head tail = &dummy; while (cur) { l = cur; r = split(l, n); cur = split(r, n); auto merged = merge(l, r); tail->next = merged.first; tail = merged.second; } } return dummy.next; } private: // Splits the list into two parts, first n element and the rest. // Returns the head of the rest. ListNode* split(ListNode* head, int n) { while (--n && head) head = head->next; ListNode* rest = head ? head->next : nullptr; if (head) head->next = nullptr; return rest; } // Merges two lists, returns the head and tail of the merged list. pair<ListNode*, ListNode*> merge(ListNode* l1, ListNode* l2) { ListNode dummy(0); ListNode* tail = &dummy; while (l1 && l2) { if (l1->val > l2->val) swap(l1, l2); tail->next = l1; l1 = l1->next; tail = tail->next; } tail->next = l1 ? l1 : l2; while (tail->next) tail = tail->next; return {dummy.next, tail}; } }; |