LeetCode148

桃扇骨 2022-01-22 20:01 204阅读 0赞

在 *O*(*n* log *n*) 时间复杂度和常数级空间复杂度下，对链表进行排序。

**示例 1:**

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

**示例 2:**

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

没有看到nlogn时间复杂度，想起用归并排序。证明对归并排序和快速排序不熟悉。

同时，即归并排序，对链表进行排序，递归的深入，有点复杂

代码：

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode sortList(ListNode head) {
            if(head == null || head.next == null)
                return head;
            
            ListNode a =head,b = head.next;
            while((b!=null)&&(b.next!=null)){
                
                head = head.next;
                b = (b.next).next;
                
            }
            b = head.next;
            head.next = null;
            return merge(sortList(a),sortList(b));
        }
        
        public ListNode merge(ListNode a,ListNode b){
            
            ListNode dummy = new ListNode(0);
            ListNode head = dummy,c= head;
            while((a!=null) && (b!=null)){
                
                if(a.val<b.val){
                    
                    c.next = a;
                    c = a;
                    a = a.next;
                }else{
                    
                    c.next = b;
                    c = b;
                    b = b.next;
                }
            }
            
            c.next = (a==null)?b:a;
            
            return head.next;
        }
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 LeetCode148--排序链表

题目分析时间复杂度限制下，符合要求的常规排序算法可以用快速，归并.....来完成，这里使用的是归并排序，归并排序最重要的的就是合并操作了，而且他合并的是两个有序集，对于

古城微笑少年丶/ 2023年01月16日 14:28/ 0 赞/ 146 阅读

相关 leetcode148.排序链表

对链表进行归并排序原题目链接 [排序链表][Link 1] 本题目要求时间复杂度为O(`n`log`n`)因此不难想到使用归并排序,而对与链表的归并排序来说,比较核

淡淡的烟草味﹌/ 2022年12月23日 03:23/ 0 赞/ 148 阅读

相关 LeetCode 148. 排序链表

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

雨点打透心脏的1/2处/ 2022年11月07日 14:33/ 0 赞/ 145 阅读

相关 LeetCode148—Sort List

原题 [原题链接][Link 1] > Sort a linked list in O(n log n) time using constant space compl

素颜马尾好姑娘i/ 2022年07月15日 03:16/ 0 赞/ 160 阅读

相关 [leetcode-排序]--148. Sort List

Question: 148. Sort List > Sort a linked list in O(n log n) time using constant space c

今天药忘吃喽~/ 2022年07月12日 00:29/ 0 赞/ 171 阅读

相关 LeetCode148. Sort List

Analysis This question requires to sort a LinkedList in `O(nlogn)` time and `O(1)` sp

女爷i/ 2022年06月08日 12:10/ 0 赞/ 168 阅读

相关 LeetCode148.链表排序

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

以你之姓@/ 2022年02月13日 05:09/ 0 赞/ 191 阅读

相关 LeetCode148

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。示例 1: 输入: 4->2->1->3 输出: 1->2->3->4 示例

桃扇骨/ 2022年01月22日 20:01/ 0 赞/ 205 阅读

相关 leetcode [148]Sort List

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

你的名字/ 2021年12月07日 14:21/ 0 赞/ 168 阅读

相关 LeetCode148. 排序链表

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。示例 1: 输入: 4->2->1->3 输出: 1->2->3->4 示例 2: 输

╰半橙微兮°/ 2021年09月27日 00:20/ 0 赞/ 291 阅读