首页 > 代码库 > 【LeetCode】Sort List

【LeetCode】Sort List

2024-07-06 20:27:50   227人阅读

Sort List

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

要求时间复杂度为O(nlogn)，那么不能用quickSort了（最坏O(n^2)），所以使用mergeSort.

通常写排序算法都是基于数组的，这题要求基于链表。所以需要自己设计函数获得middle元素，从而进行切分。

参考Linked List Cycle II中的“龟兔赛跑”思想：兔子前进两步，龟前进一步，从而可以获得middle元素。

 

class Solution {
public:
    ListNode *getMiddle(ListNode *head)
    {
        ListNode *fast = head;
        ListNode *slow = head;

        while(true)
        {
            if(fast->next != NULL)
            {
                fast = fast->next;
                if(fast->next != NULL)
                    fast = fast->next;
                else
                    break;
                slow = slow->next;
            }
            else
                break;
        }

        return slow;
    }
    ListNode *merge(ListNode *list1, ListNode *list2)
    {// merge sorted list
        ListNode *newhead = new ListNode(0);
        ListNode *head = newhead;

        while(list1 != NULL && list2 != NULL)
        {

            if(list1->val < list2->val)
            {
                newhead->next = list1;
                list1 = list1->next;
            }
            else
            {
                newhead->next = list2;
                list2 = list2->next;
            }
            newhead = newhead->next;
        }

        if(list1 == NULL)
            newhead->next = list2;
        else
            newhead->next = list1;

        return head->next;
    }
    ListNode *sortList(ListNode *head) 
    {
        if(head == NULL || head->next == NULL)
            return head;
        ListNode *mid = getMiddle(head);
        ListNode *head2 = mid->next;
        mid->next = NULL;    //attention!

        return merge(sortList(head), sortList(head2));
    }
};


联系
我们