leetcode 148. 排序链表（归并排序 快慢指针 递归 迭代）

链接：https://leetcode-cn.com/problems/sort-list/

题目

给你链表的头结点 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 * 104] 内
-105 <= Node.val <= 105

思路

方法1
递归 实现归并排序
使用快慢指针分割链表

由于使用递归O（logn）栈内存空间

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(!head||head->next==nullptr)
            return head;
        ListNode *front=head->next,*back=head;
        int index=0;
        while(front->next)
        {
            front=front->next;
            index++;
            if(index%2==0)
            {
                back=back->next;
                index=0;
            }
        }
        front=back->next;
        back->next=nullptr;
        return sort(sortList(head),sortList(front));

    }

    ListNode*sort(ListNode*a,ListNode*b)
    {
        ListNode*ha=a,*hb=b;
        ListNode*ptr=nullptr;
        if(ha->val<=hb->val)
        {
            ptr=ha;
            ha=ha->next;
        }else
        {
            ptr=hb;
            hb=hb->next;
        }
        ListNode *head=ptr;
        while(ha!=nullptr&&hb!=nullptr)
        {
            if(ha->val<=hb->val)
            {
                ptr->next=ha;
                ha=ha->next;
            }else{
                ptr->next=hb;
                hb=hb->next;
            }
            ptr=ptr->next;
        }
        if(ha!=nullptr)
        {
            ptr->next=ha;
        }
        if(hb!=nullptr)
        {
            ptr->next=hb;
        }
        return head;
    }  
};

方法2
由于进阶要求常数级空间复杂度 所以不能用递归
可以手动分割等长链表 迭代

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(!head||head->next==nullptr)
            return head;
        int num=0;
        ListNode*ptr=head;
        while(ptr)
        {
            num++;
            ptr=ptr->next;
        }
        ListNode *dhead=new ListNode(0,head);//定义头节点
        for(int lenth=1;lenthnext;//定义分支的头节点和 流动的节点
            while(cur!=nullptr)//当前节点不为空
            {
                ListNode *head1=cur;
                for(int i=1;inext!=nullptr;++i)
                {
                    cur=cur->next;
                }
                ListNode *head2=cur->next;
                cur->next=nullptr;
                cur=head2;
                for(int i=1;inext!=nullptr;++i)
                {
                    cur=cur->next;
                }
                ListNode *n =nullptr;
                if(cur!=nullptr)
                {
                    n=cur->next;
                    cur->next=nullptr;
                }
                pre->next=merge(head1,head2);
                while(pre->next!=nullptr){
                    pre=pre->next;
                }
                cur=n;
            }
        }
        return dhead->next;

    }

    ListNode* merge(ListNode* head1, ListNode* head2) {
        ListNode* dummyHead = new ListNode(0);
        ListNode* temp = dummyHead, *temp1 = head1, *temp2 = head2;
        while (temp1 != nullptr && temp2 != nullptr) {
            if (temp1->val <= temp2->val) {
                temp->next = temp1;
                temp1 = temp1->next;
            } else {
                temp->next = temp2;
                temp2 = temp2->next;
            }
            temp = temp->next;
        }
        if (temp1 != nullptr) {
            temp->next = temp1;
        } else if (temp2 != nullptr) {
            temp->next = temp2;
        }
        return dummyHead->next;
    }
};

注意

链表问题可以定义额外头节点来 规范循环条件ListNode *dhead=new ListNode(0,head)；