【leetcode每日一题】148.sort List

红太狼 2022-08-04 14:36 154阅读 0赞

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

解析：题目要求是对链表进行排序，但是复杂度不能超过O(nlgn)。符合题意的常见排序方法有快排、归并排序和堆排序。以下是用归并排序解决此题的步骤。

1）将链表从中间部分分为两个链表。具体做法是：声明两个指针，一个快指针和一个慢指针，当快指针指向NULL时，慢指针指向中间节点。

2）对左右链表进行递归，直到链表只剩一个节点为止。

3）调用归并函数，对两个链表进行归并。归并函数的实现思路，请见第21题：Merge two sorted lists http://blog.csdn.net/kevin\_zhai/article/details/47439123

代码如下：

/**
     * 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==NULL||head->next==NULL)
                return head;
            return mergesort(head);
        }
        ListNode *mergesort(ListNode *head)
        {
            if(head==NULL||head->next==NULL)
                return head;
            ListNode *fast=head,*slow=head;
            ListNode *leftHalf,*rightHalf,*pre;
            while(fast!=NULL&&fast->next!=NULL)
            {
                fast=fast->next->next;
    			pre=slow;
                slow=slow->next;
            }
            pre->next=NULL;
            leftHalf=mergesort(head);
            rightHalf=mergesort(slow);
            return merge(leftHalf,rightHalf);
        }
        ListNode *merge(ListNode *leftHalf,ListNode *rightHalf)
        {
            ListNode *result=new ListNode(0);
            ListNode *temp=result;
            while(leftHalf!=NULL&&rightHalf!=NULL)
            {
                if(leftHalf->val<rightHalf->val)
                {
                    temp->next=leftHalf;
                    temp=temp->next;
                    leftHalf=leftHalf->next;
                }
                else
                {
                    temp->next=rightHalf;
                    temp=temp->next;
                    rightHalf=rightHalf->next;
                }
            }
            if(leftHalf!=NULL)
                temp->next=leftHalf;
            if(rightHalf!=NULL)
                temp->next=rightHalf;
            temp=result->next;
            //delete result;
            return temp;
        }
    };