牛客热题：单链表排序

📟作者主页：慢热的陕西人

🌴专栏链接：力扣刷题日记

📣欢迎各位大佬👍点赞🔥关注🚓收藏，🍉留言

牛客热题：单链表排序

题目链接

单链表的排序_牛客题霸_牛客网 (nowcoder.com)

方法一：用数组排序再赋值回来

思路

• 用数组先将链表中的值存储起来
• 对数组进行排序
• 将数组的值赋值给链表

代码

    ListNode* sortInList(ListNode* head) 
    {
        vector<int> v;
        ListNode* cur = head;
        while(cur != nullptr)
        {
            v.push_back(cur->val);
            cur = cur->next;
        }

        sort(v.begin(), v.end());

        cur = head;
        for(auto & vv : v)
        {
            cur->val = vv;
            cur = cur->next;
        }
        return head;
    }

复杂度

时间复杂度：O($NlogN$),用了c++原生的sort，底层是快排。

空间复杂度；O(N),借用了额外的数组空间

方法二：归并排序

思路

• 先将原先的链表，对半分开直到不能再分(单个节点的情况)
• 然后再将他们按照有序的方式合并

分开：

• 快慢指针的思路，快指针一步走两个节点，慢指针一步走一个节点
• 当快指针到达链表结尾的时候，那么这时候，慢指针恰好就在链表的中间位置
• 我们从这块将两个链表分开就好

合并：

• 创建一个哨兵位
• 遍历比较排序好的左右单链表区间
• 并逐个比较，尾插到哨兵位

代码

    ListNode* sortInList(ListNode* head) 
    {
        if(head == nullptr || head->next == nullptr) return head;
        //快慢指针寻找链表的中点
        ListNode* fast = head->next;
        ListNode* slow = head;
        while(fast != nullptr && fast->next != nullptr)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        //将链表从中间分开
        ListNode* temp = slow->next;
        slow->next = nullptr;
        //递归左右两边进行排序
        ListNode* left = sortInList(head);
        ListNode* right = sortInList(temp);
        //创建新的链表,带有哨兵位
        ListNode* h = new ListNode(0);
        ListNode* res = h;        
        //合并left和right两个链表
        while(left != nullptr && right != nullptr)
        {
            if(left->val < right->val)
            {
                h->next = left;
                left = left->next;
            }
            else 
            {
                h->next = right;
                right = right->next;
            }
            h = h->next;
        }
        //最后查看left和right哪个还有剩余未添加的节点
        h->next = left == nullptr ? right : left;

        return res->next; 
    }

复杂度

时间复杂度:O($NlogN$),利用归并排序的思路实现。

空间复杂度:O(1),借用了常数个额外的空间。