leetcode 148 Sort List

共计 1387 个字符，预计需要花费 4 分钟才能阅读完成。

题目
https://leetcode.com/problems…
Sort a linked list in O(n log n) time using constant space complexity.
Example 1:
Input: 4->2->1->3Output: 1->2->3->4Example 2:
Input: -1->5->3->4->0Output: -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;
}
};