LeetCode 148. Sort List

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

LeetCode 148. Sort List 原题链接中等

作者：

yxc , 2018-07-17 21:51:51 , 所有人可见 , 阅读 7865

62

51

题目描述

给定一个单链表，请使用 $O(nlogn)$ 的时间复杂度和额外 $O(1)$ 的空间复杂度对其进行排序。

样例1

输入：4->2->1->3
输出：1->2->3->4

样例2

输入：-1->5->3->4->0
输出：-1->0->3->4->5

算法

(归并排序) $时间：O(nlogn)，空间O(1)$

自顶向下递归形式的归并排序，由于递归需要使用系统栈，递归的最大深度是 $logn$，所以需要额外 $O(logn)$ 的空间。
所以我们需要使用自底向上非递归形式的归并排序算法。
基本思路是这样的，总共迭代 $logn$ 次：

第一次，将整个区间分成连续的若干段，每段长度是2：$[a_0, a_1], [a_2, a_3], … [a_{n-1}, a_{n-1}]$，然后将每一段内排好序，小数在前，大数在后；
第二次，将整个区间分成连续的若干段，每段长度是4：$[a_0, …, a_3], [a_4,…, a_7], … [a_{n-4}, …, a_{n-1}]$，然后将每一段内排好序，这次排序可以利用之前的结果，相当于将左右两个有序的半区间合并，可以通过一次线性扫描来完成；
依此类推，直到每段小区间的长度大于等于 $n$ 为止；

另外，当 $n$ 不是2的整次幂时，每次迭代只有最后一个区间会比较特殊，长度会小一些，遍历到指针为空时需要提前结束。

时间复杂度分析：整个链表总共遍历 $logn$ 次，每次遍历的复杂度是 $O(n)$，所以总时间复杂度是 $O(nlogn)$。
空间复杂度分析：整个算法没有递归，迭代时只会使用常数个额外变量，所以额外空间复杂度是 O(1)$.

C++ 代码

/**
 * 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) {
        int n = 0;
        for (auto p = head; p; p = p->next) n ++ ;

        auto dummy = new ListNode(-1);
        dummy->next = head;
        for (int i = 1; i < n; i *= 2) {
            auto cur = dummy;
            for (int j = 1; j + i <= n; j += i * 2) {
                auto p = cur->next, q = p;
                for (int k = 0; k < i; k ++ ) q = q->next;
                int x = 0, y = 0;
                while (x < i && y < i && p && q) {
                    if (p->val <= q->val) cur = cur->next = p, p = p->next, x ++ ;
                    else cur = cur->next = q, q = q->next, y ++ ;
                }
                while (x < i && p) cur = cur->next = p, p = p->next, x ++ ;
                while (y < i && q) cur = cur->next = q, q = q->next, y ++ ;
                cur->next = q;
            }
        }

        return dummy->next;
    }
};

31 评论

KillLemon 2021-01-07 17:13

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        //很不熟练，利用自底向上的归并思想，每次先归并好其中一小段，之后对两小段之间进行归并
        int n = 0;
        for(auto p = head; p ; p = p->next) n ++;

        auto dummy = new ListNode(-1);
        dummy->next = head;

        for(int i = 1; i < n; i *= 2 ){ //每次归并段的长度，每次长度依次为1,2,4,8...n/2
        //小于n是因为等于n时说明所有元素均归并完毕，大于n时同理
            auto cur = dummy;
            for(int j = 1;j + i <= n; j += 2 * i){//j代表每一段的开始，每次将两段有序段归并为一个大的有序段，故而每次+2i
            //必须保证每段中间序号是小于链表长度的，显然，如果大于表长，就没有元素可以归并了
                auto p = cur->next,q = p;//p表示第一段的起始点，q表示第二段的起始点，之后开始归并即可
                for(int k = 0; k < i; k ++) q = q->next;

                //x,y用于计数第一段和第二段归并的节点个数，由于当链表长度非2的整数倍时表长会小于i,故而需要加上p && q的边界判断
                 int x = 0, y = 0;
                 while(x < i && y < i && p && q){
                     if(p->val <= q->val) cur = cur->next = p,p = p->next,x ++; //等号的赋值顺序为从右到左，故而该句意思为
                     //cur->next = p,cur = cur->next,即将小的一点插入cur链表中
                     else cur = cur->next = q,q = q->next,y++;
                 }


                //归并排序基本套路
                 while(x < i && p) cur = cur->next = p,p = p->next,x ++;
                 while(y < i && q) cur = cur->next = q,q = q->next,y ++;
                 cur->next = q; //记得把排好序的链表尾链接到下一链表的表头，循环完毕后q为下一链表表头
            }
        } 
        return dummy->next;
    }
};

KillLemon 2021-01-07 17:15

解释了一下Y总的代码，方便大家阅读

卑微小七 2021-07-18 15:29 回复了 KillLemon 的评论

对于第二段不满的情况怎么排序的？

猪啊猪 2021-11-03 13:17 回复了卑微小七的评论

就是正常排啊。。通过&&q在走到末尾的时候就终止了，而这时cur已经走过了第二段所有的点，故此时第二段的点已经完成归并排序了，接下来就是对第一段剩下的点进行归并。

清清想学算法 2023-01-17 18:08 回复了 KillLemon 的评论

感谢

美琴 2023-08-18 18:07

只有最后一段长度可能小于 $i$，前面都等于 $i$。分析见

https://www.acwing.com/activity/content/code/content/6893820/

另外 dummy 在栈上分配就不用 delete 了，也快一点。

/**
 * 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) {
        int n = 0;
        for (auto p = head; p; p = p->next) n++;

        ListNode dummy = {-1, head};
        for (int i = 1; i < n; i <<= 1) {
          auto cur = &dummy;
          for (int j = 1; j + i <= n; j += i << 1) {
            auto p = cur->next, q = p;
            int k = i;
            while (k--) q = q->next;

            int x = i, y = min(i, n - j - i + 1);
            while (x && y) {
              if (p->val <= q->val) cur = cur->next = p, p = p->next, x--;
              else cur = cur->next = q, q = q->next, y--;
            }
            while (x) cur = cur->next = p, p = p->next, x--;
            while (y) cur = cur->next = q, q = q->next, y--;
            cur->next = q;
          }
        }

        return dummy.next;
    }
};