Leetcode148. 排序链表——链表的归并排序

2021年5月10日 203点热度 1人点赞 0条评论

题目描述

给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表

进阶:

  • 你可以在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序吗?

示例 1:

img

输入:head = [4,2,1,3]
输出:[1,2,3,4]

示例 2:

img

输入:head = [-1,5,3,4,0]
输出:[-1,0,3,4,5]

示例 3:

输入:head = []
输出:[]

提示:

  • 链表中节点的数目在范围 $[0, 5 \times 10^4] $内
  • $-10^5 \leq Node.val \leq 10^5$

解题思路

链表的排序是一道很经典的题目,可以实现的排序算法有很多种。本道题主要实现了链表的归并排序。

链表的归并排序的思想与数组的归并排序并无二致,也可以分为递归迭代两种方式来实现。

在具体的实现过程中主要有以下几点差别:

  • 在数组中需要合并两个有序数组,那么在链表中就需要合并两个有序链表。具体实现方法可以参见Leetcode21.合并两个有序链表

  • 在链表的归并排序中,需要有断链的操作,否则会出现错误。

代码如下所示:

示例代码

迭代版:

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

ListNode* mergerTwoList(ListNode* firstHead,ListNode* secondHead)
{
    //合并两个有序链表
    if(!firstHead) return secondHead;
    if(!secondHead) return firstHead;

    ListNode* virtualHead=new ListNode(0);
    ListNode* firstPtr=firstHead;
    ListNode* secondPtr=secondHead;
    ListNode* curPtr=virtualHead;
    while(firstPtr&&secondPtr)
    {
        if(firstPtr->val<secondPtr->val)
        {
            curPtr->next=firstPtr;
            firstPtr=firstPtr->next;
            curPtr=curPtr->next;
            curPtr->next=nullptr;
        }
        else{
            curPtr->next=secondPtr;
            secondPtr=secondPtr->next;
            curPtr=curPtr->next;
            curPtr->next=nullptr;
        }
    }
    if(firstPtr) curPtr->next=firstPtr;
    if(secondPtr) curPtr->next=secondPtr;
    return virtualHead->next;
}

ListNode* findMidPtr(ListNode* head)
{
    //获取中间结点
    if(head==nullptr||head->next==nullptr) return head;

    ListNode* fastPtr=head->next->next;
    ListNode* slowPtr=head;
    if(fastPtr&&fastPtr->next)
    {
        fastPtr=fastPtr->next->next;
        slowPtr=slowPtr->next;
    }

    return slowPtr;
}

ListNode* sortList(ListNode* head)
{
    if(head==nullptr||head->next==nullptr) return head;

    ListNode* midPtr=findMidPtr(head);
    ListNode* rightHead=midPtr->next;
    midPtr->next=nullptr;
    ListNode* leftPtr=sortList(head);
    ListNode* rightPtr=sortList(rightHead);
    return mergerTwoList(leftPtr,rightPtr);
}

时间复杂度:$O(nlogn)$

空间复杂度:$O(logn)$

迭代版:

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

ListNode* mergerTwoList(ListNode* firstHead,ListNode* secondHead)
{
    //合并两个有序链表
    if(!firstHead) return secondHead;
    if(!secondHead) return firstHead;

    ListNode* virtualHead=new ListNode(0);
    ListNode* firstPtr=firstHead;
    ListNode* secondPtr=secondHead;
    ListNode* curPtr=virtualHead;
    while(firstPtr&&secondPtr)
    {
        if(firstPtr->val<secondPtr->val)
        {
            curPtr->next=firstPtr;
            firstPtr=firstPtr->next;
            curPtr=curPtr->next;
            curPtr->next=nullptr;
        }
        else{
            curPtr->next=secondPtr;
            secondPtr=secondPtr->next;
            curPtr=curPtr->next;
            curPtr->next=nullptr;
        }
    }
    if(firstPtr) curPtr->next=firstPtr;
    if(secondPtr) curPtr->next=secondPtr;
    return virtualHead->next;
}

int getLength(ListNode* head)
{
    //获得链表长度
    int length=0;
    while(head!=nullptr)
    {
        length++;
        head=head->next;
    }
    return length;
}

ListNode* split(ListNode* head,int step)
{
    //断链,返回第二部分链表的头结点
    if(head==nullptr) return head;
    ListNode* cur=head;
    for(int i=1;i<step&&cur->next!=nullptr;++i)
    {
        cur=cur->next;
    }
    ListNode* right=cur->next;
    cur->next=nullptr;
    return right;
}

ListNode* sortList(ListNode* head)
{
    if(head==nullptr||head->next==nullptr) return head;
    int length=getLength(head);

    ListNode* virtualHead=new ListNode(-1,head);
    //步长从1,2,4,...,一直到length
    for(int subLength=1;subLength<length;subLength*=2)
    {
        //pre指针指向已经排好序的链表末尾,cur指针指向将要进行处理的链表的头结点
        ListNode* pre=virtualHead;
        ListNode* cur=virtualHead->next;

        //while循环处理一次步长的所有合并操作
        while(cur!=nullptr)
        {
            //head1为第一部分头
            ListNode* head1=cur;
            //head2为第二部分头
            ListNode* head2=split(head1,subLength);
            //cur为剩余需要处理的链表的头
            cur=split(head2,subLength);
            //合并一二部分
            ListNode* merged=mergerTwoList(head1,head2);
            //更新其他指针的状态
            pre->next=merged;
            while(pre->next!=nullptr)
            {
                pre=pre->next;
            }
        }
    }
    return virtualHead->next;
}

时间复杂度:$O(nlogn)$

空间复杂度:$O(1)$

agedcat_xuanzai

这个人很懒,什么都没留下

文章评论