LeetCode刷题（C++）——Sort List（Medium）

た入场券 2022-06-15 01:19 167阅读 0赞

**Sort a linked list in O(n log n) time using constant space complexity.**

/**
     * 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) {
            if(head==NULL || head->next==NULL){
                return head;
            }
            ListNode* a=head, *b=head;
            while(b->next && b->next->next){
                a=a->next;
                b=b->next->next;
            }
            b=sortList(a->next);
            a->next=NULL;
            a=sortList(head);
            ListNode* tail=NULL;
            while(a && b){
                if(a->val < b->val){
                    if(tail){
                        tail=tail->next=a;
                    }
                    else{
                        head=tail=a;
                    }
                    a=a->next;
                }
                else{
                    if(tail){
                        tail=tail->next=b;
                    }
                    else{
                        head=tail=b;
                    }
                    b=b->next;
                }
            }
            if(a){
                if(tail){
                    tail->next=a;
                }
                else{
                    head=tail;
                }
            }
            else{
                if(tail){
                    tail->next=b;
                }
                else{
                    head=b;
                }
            }
            return head;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，167人围观）

还没有评论，来说两句吧...

相关阅读

相关 Leetcode 刷题

* [Leetcode 9. 回文数][Leetcode 9.] * [Leetcode 125. 验证回文串][Leetcode 125.] * [Leetc...

た入场券/ 2024年04月18日 12:09/ 0 赞/ 84 阅读

相关 leetcode刷题纪要

2020-01-11 给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。

ゞ浴缸里的玫瑰/ 2023年01月05日 01:26/ 0 赞/ 122 阅读

相关 LeetCode刷题目录

<table> <tbody> <tr> <th colspan="3">LeetCode刷题目录</th> </tr> <tr> <th

待我称王封你为后i/ 2022年12月29日 04:53/ 0 赞/ 155 阅读

相关 LeetCode刷题笔记

文章目录 1.数据结构 1.1字符串、数组、链表 1.2队列、栈 1.3堆 1.4树 1.

向右看齐/ 2022年11月19日 07:54/ 0 赞/ 242 阅读

相关 leetcode刷题记录

\\ leetcode刷题记录 \\ 别人的刷题记录：[leetcode题解一览表][leetcode] 1052. 爱生气的书店老板看到了位置可选的长度

野性酷女/ 2022年10月31日 15:53/ 0 赞/ 194 阅读

相关 [leetcode]: 刷题目录

题目分类，博客对应连接，方便查找 1.树路径和 [112. Path Sum][] [437. Path Sum III][] 遍历 [104. Maxi

女爷i/ 2022年06月15日 11:17/ 0 赞/ 227 阅读

相关 LeetCode刷题答案

目录 3. 无重复字符的最长子串 4. 寻找两个有序数组的中位数 5. 最长的回文子串 6.Z 字形变换 8. 字符串转换整数 (atoi) 9. 回文数

比眉伴天荒/ 2022年04月24日 09:46/ 0 赞/ 295 阅读

相关 LeetCode刷题指南

以下是我个人做题过程中的一些体会： 1. LeetCode的题库越来越大，截止到目前，已经有321个问题了。对于大多数人来说，没有时间也没有必要把所有题目都做一遍（时间充

àì夳堔傛蜴生んèń/ 2022年02月04日 20:30/ 0 赞/ 310 阅读

相关 Leetcode Database 刷题

文章目录 175. 组合两个表 176. 第二高的薪水 177. 第N高的薪水 178. 分数排名 180. 连续出现的数字 181.

左手的ㄟ右手/ 2021年10月15日 12:21/ 0 赞/ 640 阅读

相关 Leetcode刷题

39. 组合总和给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

秒速五厘米/ 2021年06月10日 20:37/ 0 赞/ 569 阅读