链表O(n log n)排序

sortlist.md

Sort List

Sort a linked list in O(n log n) time using constant space complexity.

思路

• 归并，复杂度O(n log n)
• 递归至两个节点，合并两个链表

        /**
         * 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 == nullptr || head->next == nullptr){
                    return head;
                }
                ListNode *fast = head;
                ListNode *slow = head;
                
                while(fast->next != nullptr && fast->next->next != nullptr){
                    //two steps
                    fast = fast->next->next;
                    //one step
                    slow = slow->next;
                }
                
                //separate into two lists
                fast = slow;
                slow = slow->next;
                fast->next = nullptr;
                
                ListNode *p1 = sortList(head);
                ListNode *p2 = sortList(slow);
                
                return mergeTwoLists(p1,p2);
            }
            ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
                if(l1 == nullptr){
                    return l2;
                }else if(l2 == nullptr){
                    return l1;
                }
                ListNode* pMergedHead = nullptr;
                if(l1->val < l2->val){
                    pMergedHead = l1;
                    pMergedHead->next = mergeTwoLists(l1->next,l2);
                }else{
                    pMergedHead = l2;
                    pMergedHead->next = mergeTwoLists(l1,l2->next);
                }
                return pMergedHead;
            }
        };