牛客在线编程101-12 单链表的排序

川长思鸟来 2023-10-04 19:39 58阅读 0赞

### 题目 ###

给定一个节点数为n的无序单链表，对其按升序排序。

数据范围：0 < n \\le 1000000<n≤100000  
要求：空间复杂度 O(n)O(n)，时间复杂度 O(nlogn)O(nlogn)

### 解析 ###

方法有很多种，可以对链表排序，这个有难度，还可以对链表的值排序  
对值内容排序，再分别赋给

import java.util.*;
    
    /*
     * public class ListNode {
     *   int val;
     *   ListNode next = null;
     * }
     */
    
    public class Solution {
        
        /**
         * 
         * @param head ListNode类 the head node
         * @return ListNode类
         */
        public ListNode sortInList (ListNode head) {
        
            // write code here
            ArrayList<Integer> list = new ArrayList<>();
            ListNode cur = head;
            while(cur != null) {
        
                list.add(cur.val);
                cur = cur.next;
            }
    
            Collections.sort(list);
    
            if(list.size() != 0) {
        
                head.val = list.get(0);
                cur = head;
                for(int i = 1; i < list.size(); i++) {
        
                    cur.next.val = list.get(i);
                    cur = cur.next;
                }
            } 
            return head;
        }
    }

发表评论取消回复

表情：

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

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

相关阅读

相关算法练习（5）：牛客在线编程01 链表

package jz.bm; import jz.ListNode; import java.util.ArrayList;

深藏阁楼爱情的钟/ 2023年10月14日 16:18/ 0 赞/ 52 阅读

相关牛客在线编程101-4 合并两个排序的链表

题目输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。数据范围： 0 \\le n \\le 10000≤n≤1000，-1

傷城~/ 2023年10月04日 19:44/ 0 赞/ 44 阅读

相关牛客在线编程101-6 判断链表中是否有环

题目判断给定的链表中是否有环。如果有环则返回true，否则返回false。解析 / Definition for singly-linked

超、凢脫俗/ 2023年10月04日 19:43/ 0 赞/ 52 阅读

相关牛客在线编程101-6 判断链表中是否有环

题目判断给定的链表中是否有环。如果有环则返回true，否则返回false。解析 / Definition for singly-linked

深碍√TFBOYSˉ_/ 2023年10月04日 19:43/ 0 赞/ 52 阅读

相关牛客在线编程101-11链表相加(二)

题目假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。给定两个这种链表，请生成代表两个整数相加值的结果链表。数据范围：0 \\l

我就是我/ 2023年10月04日 19:41/ 0 赞/ 56 阅读

相关牛客在线编程101-12 单链表的排序

题目给定一个节点数为n的无序单链表，对其按升序排序。数据范围：0 < n \\le 1000000<n≤100000 要求：空间复杂度 O(n)O(n)，时间复

川长思鸟来/ 2023年10月04日 19:39/ 0 赞/ 59 阅读

相关牛客在线编程101-14 链表的奇偶重排

题目给定一个单链表，请设定一个函数，将链表的奇数位节点和偶数位节点分别放在一起，重排后输出。注意是节点的编号而非节点的数值。数据范围：节点数量满足 0 \\l

旧城等待，/ 2023年10月04日 19:39/ 0 赞/ 17 阅读

相关牛客在线编程101-02链表内指定区间反转

题目将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n)O(n)，空间复杂度 O(1)O(1)。例如：给出的链表为

深藏阁楼爱情的钟/ 2023年10月04日 19:32/ 0 赞/ 59 阅读

相关牛客在线编程101-01反转链表

题目：描述：给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。数据范围： 0\\leq n\

左手的ㄟ右手/ 2023年10月04日 19:31/ 0 赞/ 61 阅读

相关牛客网——单链表反转

![在这里插入图片描述][59695ff5471e433bb0d41964fe2a339e.gif_pic_center] > 个人主页：[熬夜磕代码丶][Link 1]

朴灿烈づ我的快乐病毒、/ 2023年09月28日 22:02/ 0 赞/ 20 阅读