leetcode148. Sort List

leetcode148. Sort List

题意：

使用恒定空间复杂度在O（nlogn）时间内对链表进行排序。

思路：

merge排序，不断二分，然后归并，返回新的链表，归并链表。

• 用slow和fast指针找到mid点，并且要注意的是结束的时候slow指针已经是mid + 1的点了，如果还让right区间划分为[slow + 1,]就会死循环,假设只有两个元素容易验证。
• 给链表排序，有点骚气。

ac代码：

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* getMid(ListNode* head)
    {
        if(!head) return NULL;        
        ListNode* slow = head;
        ListNode* fast = head;
        ListNode* mid = slow;
        while(fast&&fast->next)
        {
            mid = slow;
            slow = slow->next;
            fast = fast->next->next;
        }       
        mid->next = NULL;
        return slow;
    }
    
    ListNode* sortList(ListNode* head) 
    {
        if(!head) return NULL;
        if(!head->next) return head;
        ListNode* res = new ListNode(0);
        ListNode* pos = res;
        ListNode* mid = getMid(head);
        ListNode* left = sortList(head);
        ListNode* right = sortList(mid);
        while(left&&right)
        {
            if(left->val < right->val)
            {
                pos->next = new ListNode(left->val);
                left = left->next;
            }
            else
            {
                pos->next = new ListNode(right->val);
                right = right->next;
            }
            pos = pos->next;
        }
        pos->next = !left?right:left;
        return res->next;
    }
};

python