LeetCode 148. Sort List [Medium] [C++] 解題筆記

 Given the head of a linked list, return the list after sorting it in ascending order.

Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?

 

Example 1:

Input: head = [4,2,1,3]
Output: [1,2,3,4]

Example 2:

Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]

Example 3:

Input: head = []
Output: []

 

Constraints:

• The number of nodes in the list is in the range [0, 5 * 104].
• -105 <= Node.val <= 105

想法:

    這題要我們排序一個 linked-list，並且要求在 O(nlogn) time。 要在 O(nlogn) time 完成排序自然需要利用 quick sort, heap sort, 或是 merge sort 之類的方式，但是題目同時要求要在 O(1) space 下完成排序，因此 quick sort 是利用 divide & conquer 的技巧需要 recursive 的求解因此遞迴時會用到 stack的空間最壞情況下空間複雜度會來到 O(n)，而 heap sort 在過程中也需要用到 heap 空間複雜度同樣是 O(n)。因此這題最適合的是用 merge-sort buttom up 的實作方式 (top-down 也是遞迴求解因此空間複雜度為O(nlogn)) 才能達到 O(1) 的空間複雜度。

完整程式碼:

/* merge sort (top-down)

* O(nlogn) time

* O(nlogn) space (recursive)

*/

class Solution {

public:

ListNode* sortList(ListNode* head) {

// remain 0 or 1

if (head == NULL || head->next == NULL) {

return head;

}

ListNode* slow = head;

ListNode* fast = head->next;

while (fast != NULL && fast->next != NULL) {

slow = slow->next;

fast = fast->next->next;

}

ListNode* mid = slow->next;

slow->next = nullptr;

return merge(sortList(head), sortList(mid));

}

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;

}

if (l1) { tail->next = l1; }

if (l2) { tail->next = l2; }

return dummy.next;

}

};

/* merge sort bottom up

* O(nlogn) time

* O(1) space

*/

class Solution {

public:

ListNode* sortList(ListNode* head) {

// remain 0 or 1

if (head == NULL || head->next == NULL) {

return head;

}

// compute len of list

int len = 0;

auto cur = head;

while (cur) {

cur = cur->next;

len++;

}

ListNode dummy(0);

dummy.next = head;

ListNode* left;

ListNode* right;

// record the tail of current merged sublist

ListNode* tail;

for (int n = 1; n < len; n <<= 1) {

cur = dummy.next;

tail = &dummy;

while (cur) {

left = cur;

right = split(left, n);

cur = split(right, n);

auto merged = merge(left, right);

// the head of merged sublist

tail->next = merged.first;

// the tail of merged sublist

tail = merged.second;

}

}

return dummy.next;

}

// split the list to first n element and remaining part, return the head of remaining part.

// ex: 4->2->1->3 and n = 1, then remaining part is 2->1->3

ListNode* split (ListNode* head, int n) {

while (--n && head) {

head = head->next;

}

auto remain = (head)? head->next : nullptr;

if (head) { head->next = nullptr; }

return remain;

}

// return the head after merge and tail of the merged sublist

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;

}

if (l1) { tail->next = l1; }

if (l2) { tail->next = l2; }

while (tail->next) { tail = tail->next; }

return {dummy.next, tail };

}

};