148. Sort List

• 方法1:
• • 易錯點：
  • Complexity
• 方法2:

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
           

方法1:

思路：

考慮到題目要求，必須是constant space而且是O(nlogn)時間，最合适linked list的sort是merge sort。那麼這道題就相當于兩個子問題的結合：1. 将原鍊切分成左右子鍊，2. 左右子鍊的merge two sorted linked list 。

易錯點：

1. slow要找的是右中位
2. newhead在兩個函數裡都是必須的
3. 找到slow的位置後，需要把鍊切開，是以還需要一個prev, 最後将prev -> next = nullptr

Complexity

Time complexity: O(nlogn)

Space complexity: O(1)

/**
 * 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) {
        if (!head || !head -> next) return head;
        
        ListNode* newHead = new ListNode(-1);
        newHead -> next = head;
        ListNode* slow = head, *fast = head, *prev = newHead;
        while (fast && fast -> next) {
            prev = slow;
            slow = slow -> next;
            fast = fast -> next -> next;
        }
        prev -> next = nullptr;
        return sortHelper(sortList(head), sortList(slow));
    }
    
    ListNode* sortHelper(ListNode* l1, ListNode* l2) {
        ListNode* newHead = new ListNode(-1);
        ListNode* prev = newHead;
        while (l1 && l2) {
            if (l1 -> val <= l2 -> val) {
                prev -> next = l1;
                l1 = l1 -> next;
            }
            else {
                prev -> next = l2;
                l2 = l2 -> next;
            }
            prev = prev -> next;
        }
        if (l1) prev -> next = l1;
        if (l2) prev -> next = l2;
        return newHead -> next;
    }
};
           

方法2:

思路：

原理一樣，helper的部分改成了遞歸式。

/**
 * 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) {
        if (!head || !head -> next) return head;
        
        ListNode* newHead = new ListNode(-1);
        newHead -> next = head;
        ListNode* slow = head, *fast = head, *prev = newHead;
        while (fast && fast -> next) {
            prev = slow;
            slow = slow -> next;
            fast = fast -> next -> next;
        }
        prev -> next = nullptr;
        return sortHelper(sortList(head), sortList(slow));
    }
    
    ListNode* sortHelper(ListNode* l1, ListNode* l2) {
        if (!l1) return l2;
        if (!l2) return l1;
        if (l1 -> val < l2 -> val) {
            l1 -> next = sortHelper(l1 -> next, l2);
            return l1;
        } else {
            l2 -> next = sortHelper(l1, l2 -> next);
            return l2;
        }
    }
};