leetcode 148 Sort List

题目

https://leetcode.com/problems...

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

思路

类似快排的思路，进行递归partition。主要是注意处理一些边界条件。
每次对一个子段进行sort了之后，要处理好其和原先整链的首尾重新连接好。

代码

/**
 * 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) {
        return sortList(head, NULL);
    }
    
private:
    // sort [beg, end), and return new head, and tail->next = end;
    ListNode* sortList(ListNode*beg, ListNode* end) {
        if (beg == end || !beg || beg->next == end) {
            return beg;
        }
        // at least has two node
        // [head, mid, end], maybe head == mid == end
        // [head, mid) < mid < [mid->next, end)
        ListNode* head = NULL; // new head
        ListNode* mid = NULL;
        beg = partition(beg, end, &head, &mid);
        
        // sort [mid->next, end)
        if (mid && mid->next != end) {
            mid->next = sortList(mid->next, end);
        }
        // sort [head, mid)
        return sortList(head, mid);
    }
    
    ListNode* partition(ListNode* beg, ListNode* end,
                   ListNode** p_head, ListNode** p_mid) {
        if (!beg || !p_head || !p_mid) {
            return beg;
        }
        ListNode* mid = beg;
        ListNode* tail1 = NULL;
        ListNode* tail2 = NULL;
        int v = mid->val;
        ListNode* p = mid->next;
        while (p != end) {
            if (p->val < v) {
                if (!*p_head) {
                    *p_head = p;
                    tail1 = p;
                } else {
                    tail1->next = p;
                    tail1 = p;
                }
            } else {
                if (!tail2) {
                    mid->next = p;
                    tail2 = p;
                } else {
                    tail2->next = p;
                    tail2 = p;
                }
            }
            p = p->next;
        }
        if (tail1) { tail1->next = mid; }
        else { *p_head = mid; }
        if (tail2) { tail2->next = end; }
        else { mid->next = end; }
        *p_mid = mid;
        return *p_head;
    }
};