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

题目描述

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

进阶：

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

示例 1：

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

示例 2：

输入：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)$