给定一个节点数为n的无序单链表，对其按升序排序。
数据范围：
，保证节点权值在![[-10^9,10^9]](https://www.nowcoder.com/equation?tex=%5B-10%5E9%2C10%5E9%5D)
之内。
要求：空间复杂度 )
，时间复杂度 )
[编程题]单链表的排序
import java.util.*;
public class Solution {
public ListNode sortInList (ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode slow = dummyHead;
ListNode fast = dummyHead;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode list2 = slow.next;
slow.next = null;
ListNode left = sortInList(dummyHead.next);
ListNode right = sortInList(list2);
return merge(left, right);
}
private ListNode merge(ListNode list1, ListNode list2) {
ListNode dummyHead = new ListNode(0);
ListNode p = dummyHead;
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
p.next = list1;
list1 = list1.next;
} else {
p.next = list2;
list2 = list2.next;
}
p = p.next;
}
p.next = list1 == null ? list2 : list1;
return dummyHead.next;
}
}
发表于 2024-09-17 16:17:16
回复(0)
家人们 这个思路也是按照官方的来 拆成K个链表的合并， 为啥就超时了呢！是不是哪里有bug，大佬帮忙看看
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* public ListNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类 the head node
* @return ListNode类
*/
public ListNode sortInList (ListNode head) {
List<ListNode> splitSortedNodeList = splitSortedNodeList(head);
return mergeKNodeList(splitSortedNodeList);
}
// 把这个无序链表拆成若干个有序的链表
List<ListNode> splitSortedNodeList(ListNode head) {
List<ListNode> list = new LinkedList<>();
ListNode curr = head;
while (curr != null) {
ListNode innerHead = curr;
list.add(innerHead);
while (null != innerHead) {
ListNode innerHeadNext = innerHead.next;
if (null == innerHeadNext) {
curr = null;
break;
}
if (innerHead.val > innerHeadNext.val) {
curr = innerHeadNext;
innerHead.next = null;
break;
}
innerHead = innerHead.next;
}
}
// 打印看一下拆成若干个有序的链表的结果
list.forEach(t -> {
ListNode x = t;
while (x != null) {
System.out.print(x.val + " ");
x = x.next;
}
System.out.println("");
});
return list;
}
// K个链表合并
ListNode mergeKNodeList(List<ListNode> list) {
return divideMergeNodeList(
list,
0,
list.size() - 1
);
}
// 归并合并
ListNode divideMergeNodeList(List<ListNode> list, int left, int right) {
if (left > right) {
return null;
}
if (left == right) {
return list.get(left);
}
int mid = (left + right) / 2;
return merge2NodeList(
divideMergeNodeList(list, left, mid),
divideMergeNodeList(list, mid + 1, right)
);
}
// 合并2个链表
ListNode merge2NodeList(ListNode pHead1, ListNode pHead2) {
ListNode tmp = new ListNode(-1);
ListNode curr = tmp;
while (pHead1 != null || pHead2 != null) {
if (null == pHead1) {
curr.next = pHead2;
break;
} else if (null == pHead2) {
curr.next = pHead1;
break;
} else if (pHead1.val < pHead2.val) {
curr.next = pHead1;
pHead1 = pHead1.next;
} else {
curr.next = pHead2;
pHead2 = pHead2.next;
}
curr = curr.next;
}
return tmp.next;
}
}
发表于 2024-09-04 14:03:51
回复(0)
public ListNode sortInList (ListNode head) {
return sort5(head);
}
public void print(ListNode head){
while (head != null){
System.out.print(head.val);
System.out.print(",");
head = head.next;
}
System.out.println();
}
public void print(ArrayList<ListNode> list){
for(int i=0;i<list.size();i++){
System.out.print(list.get(i).val);
System.out.print(",");
}
System.out.println();
}
// 转数组，自排序
public ListNode sort5(ListNode head){
ArrayList<ListNode> list = new ArrayList<>();
while(head != null){
list.add(head);
head = head.next;
}
Collections.sort(list,(s1,s2) -> s1.val-s2.val);
ListNode const_node = new ListNode(999);
ListNode pre = const_node;
for(int i=0;i<list.size();i++){
pre.next = list.get(i);
pre = pre.next;
}
pre.next = null;
return const_node.next;
}
//转数组
public ListNode sort4(ListNode head){
print(head);
ArrayList<ListNode> list = new ArrayList<>();
while(head != null){
list.add(head);
head = head.next;
}
print(list);
sort4_1(list,0,list.size()-1);
ListNode const_node = new ListNode(999);
ListNode pre = const_node;
for(int i=0;i<list.size();i++){
pre.next = list.get(i);
pre = pre.next;
}
pre.next = null;
return const_node.next;
}
public void sort4_1(ArrayList<ListNode> list,int s,int e){
if(s == e) return;
int m = (s+e)/2;
sort4_1(list,s,m);
sort4_1(list,m+1,e);
int m_tmp = m;
ListNode node1,node2;
while(s <= m_tmp && m+1 <= e){
System.out.println(s);
System.out.println(m);
System.out.println(e);
node1 = list.get(s);
node2 = list.get(m+1);
if(node1.val > node2.val){
list.remove(m+1);
list.add(s,node2);
s++;
m++;
m_tmp++;
}else{
s++;
}
print(list);
}
System.out.println("===");
}
// 递归
public ListNode sort3(ListNode head){
if(head == null || head.next == null) return head;
ListNode slow = head;
ListNode fast = head.next;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
}
ListNode node2 = sort3(slow.next);
slow.next = null;
ListNode node1 = sort3(head);
return sort3_merge(node1,node2);
}
public ListNode sort3_merge(ListNode node1,ListNode node2){
ListNode const_node = new ListNode(99);
ListNode pre = const_node;
while(node1 != null && node2 != null){
if(node1.val < node2.val){
pre.next = node1;
node1 = node1.next;
}else{
pre.next = node2;
node2 = node2.next;
}
pre = pre.next;
}
if(node1 != null) pre.next = node1;
if(node2 != null) pre.next = node2;
return const_node.next;
}
// 插入排序
public ListNode sort2 (ListNode head) {
if(head == null) return head;
ListNode const_node = new ListNode(999);
const_node.next = head;
ListNode node1 = head;
while(node1!= null && node1.next != null){
ListNode node2 = const_node;
boolean is_insert = false;
if(node1.next.val >= node1.val){
node1 = node1.next;
continue;
}
while(node2.next != node1.next){
if(node1.next.val < node2.next.val){
ListNode tmp = node1.next;
node1.next = node1.next.next;
tmp.next = node2.next;
node2.next = tmp;
node1 = node1;
is_insert = true;
break;
}
node2 = node2.next;
}
System.out.println(node1.val);
print(head);
if(!is_insert) node1 = node1.next;
}
return const_node.next;
}
// 冒泡排序
public ListNode sort1 (ListNode head) {
if(head == null) return head;
ListNode const_node = new ListNode(999);
const_node.next = head;
ListNode pre_node = const_node.next;
ListNode next_node = pre_node.next;
while(pre_node.next != null){
if(next_node.val < pre_node.val){
int tmp = next_node.val;
next_node.val = pre_node.val;
pre_node.val = tmp;
}
next_node = next_node.next;
if(next_node == null){
pre_node = pre_node.next;
next_node = pre_node.next;
}
}
return const_node.next;
}
发表于 2024-08-19 01:02:27
回复(0)
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* public ListNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类 the head node
* @return ListNode类
*/
public ListNode sortInList (ListNode head) {
// write code here
// 借助小根堆实现 - 注意别忘了自定义类的排序需要写比较器
// 算法时间复杂度O(NlogN)，额外空间复杂度O(N)
// 1.先排除null和单值
if(head == null || head.next == null) {
// 无需排序
return head;
}
// 2.遍历链表，依次将结点入堆
PriorityQueue<ListNode> minHeap = new PriorityQueue<>((o1, o2) -> o1.val - o2.val);
ListNode cur = head;
while (cur != null) {
// 堆的插入 - offer
minHeap.offer(cur);
System.out.println("结点入堆：" + cur.val);
cur = cur.next;
}
// 3.依次出堆，尾插法建立result链表
ListNode result = null;
ListNode tail = result;
while(!minHeap.isEmpty()) {
// 依次弹出堆中所有结点，使用尾插法将它们连接起来
// 堆的弹出 - poll
ListNode rootNode = minHeap.poll();
System.out.println("结点出堆：" + rootNode.val);
rootNode.next = null;
if (tail == null) {
// 尾插第一个元素
result = rootNode;
tail = result;
} else {
tail.next = rootNode;
tail = rootNode;
}
}
// 4.返回结果链表的头结点result
return result;
}
}
发表于 2024-07-26 23:57:00
回复(0)
最小堆排序，时间复杂度为 nlogn
public ListNode sortInList (ListNode head) {
Queue<Integer> queue = new PriorityQueue<>();
ListNode index = head;
while(index != null){
queue.add(index.val);
index = index.next;
}
ListNode node = new ListNode(-1);
index = node;
while(!queue.isEmpty()){
index.next = new ListNode(queue.poll());
index = index.next;
}
return node.next;
}
发表于 2024-07-14 21:44:08
回复(0)
public ListNode sortInList (ListNode head) {
// write code here
PriorityQueue<ListNode> queue=new PriorityQueue<ListNode>(new Comparator<ListNode>(){
@Override
public int compare(ListNode l1 ,ListNode l2){
return l2.val-l1.val;
}
});;
while(head!=null){
queue.add(head);
head=head.next;
}
ListNode pre=new ListNode(0);
while(!queue.isEmpty()){
ListNode node=queue.poll();
node.next=pre.next;
pre.next=node;
}
return pre.next;
}
发表于 2024-05-26 15:41:30
回复(0)
public ListNode sortInList (ListNode head) {
// write code here
ArrayList<Integer> nums = new ArrayList<Integer>();
nums.add(head.val);
while(head.next != null){
head = head.next;
nums.add(head.val);
}
Collections.sort(nums);
ListNode newHead = new ListNode(-1);
ListNode temp = newHead;
for(int i=0; i< nums.size(); i++){
ListNode num = new ListNode(nums.get(i));
temp.next = num;
temp = temp.next;
}
return newHead.next;
}
编辑于 2023-12-20 09:44:03
回复(0)
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* public ListNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类 the head node
* @return ListNode类
*/
public ListNode sortInList (ListNode head) {
if(head==null) return null;
ListNode p = head;
List<Integer> list = new ArrayList<>();
while(p!=null){
list.add(p.val);
p=p.next;
}
p=head;
Collections.sort(list);
int[] arr= list.stream().mapToInt(Integer::valueOf).toArray();
for(int i=0;i<list.size();i++){
p.val=arr[i];
p=p.next;
}
return head;
}
}
发表于 2023-10-11 14:57:40
回复(0)
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* public ListNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类 the head node
* @return ListNode类
*/
public ListNode sortInList (ListNode head) {
// write code here
if (head == null || head.next == null) {
return head;
}
ListNode mid = findMiddle(head);
ListNode right = sortInList(mid.next);
mid.next = null;
ListNode left = sortInList(head);
return merge(left, right);
}
public ListNode findMiddle(ListNode head) {
if (head == null) {
return head;
}
ListNode slow = head, fast = head.next;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
public ListNode merge (ListNode head1, ListNode head2) {
if (head1 == null) {
return head2;
}
if (head2 == null) {
return head1;
}
if (head1.val < head2.val) {
head1.next = merge(head1.next, head2);
return head1;
} else {
head2.next = merge(head1, head2.next);
return head2;
}
}
}
发表于 2023-10-11 11:03:39
回复(0)
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类 the head node
* @return ListNode类
*/
int count = 0;
public ListNode sortInList (ListNode head) {
// write code here
return diviveAndMerge(head);
}
public ListNode diviveAndMerge(ListNode head) {
// 链表为空或只有一个元素时返回
if (head == null || head.next == null) return head;
// 中点的前序节点，即左侧节点
ListNode left = head;
// 中心节点
ListNode mid = head.next;
// 右侧节点
ListNode rigth = head.next.next;
while (rigth != null && rigth.next != null) {
left = left.next;
mid = mid.next;
// 右侧节点速度是左侧节点的2倍
rigth = rigth.next.next;
}
// 将链表从left与mid之间断开，切分成head和mid两部分
left.next = null;
// 递的过程不断将集合化为两半
ListNode node1 = diviveAndMerge(head);
ListNode node2 = diviveAndMerge(mid);
// 归的过程将两个链表合并，返回值为合并后的头节点
return mergeTwoListNode(node1, node2);
}
// 合并两个链表
public ListNode mergeTwoListNode(ListNode pHead1, ListNode pHead2) {
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
while (pHead1 != null && pHead2 != null) {
if (pHead1.val <= pHead2.val) {
cur.next = pHead1;
pHead1 = pHead1.next;
} else {
cur.next = pHead2;
pHead2 = pHead2.next;
}
cur = cur.next;
}
cur.next = pHead1 != null ? pHead1 : pHead2;
return dummy.next;
}
发表于 2023-09-25 20:40:02
回复(0)
public ListNode sortInList(ListNode head) {
int l = 0;
ListNode h = head;
while (h != null) {
l++;
h = h.next;
}
Integer[] arr = new Integer[l];
h = head;
int i = 0;
while (h != null) {
arr[i++] = h.val;
h = h.next;
}
Integer[] tmp = new Integer[arr.length];
mergeSort(arr, tmp, 0, arr.length - 1);
i = 0;
h = head;
while (h != null) {
h.val = arr[i++];
h = h.next;
}
return head;
}
private void mergeSort(Integer[] arr, Integer[] tmp, int l, int r) {
if (l < r) {
int c = (l + r) / 2;
mergeSort(arr, tmp, l, c);
mergeSort(arr, tmp, c + 1, r);
merge(arr, tmp, l, c, c + 1, r);
}
}
private void merge(Integer[] arr, Integer[] tmp, int l1, int t1, int l2, int t2) {
int tmpIdx = l1;
int start = l1;
while (l1 <= t1 && l2 <= t2) {
tmp[tmpIdx++] = arr[l1] < arr[l2] ? arr[l1++] : arr[l2++];
}
while (l1 <= t1) {
tmp[tmpIdx++] = arr[l1++];
}
while (l2 <= t2) {
tmp[tmpIdx++] = arr[l2++];
}
for (int i = start; i < tmpIdx; i++) {
arr[i] = tmp[i];
}
}
发表于 2023-09-12 23:15:36
回复(0)
家人们谁懂啊，用快排的思想可以做吗？
22/23测试用例。
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* public ListNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类 the head node
* @return ListNode类
*/
public ListNode sortInList (ListNode head) {
if(head == null || head.next == null) return head;
ListNode dummy1 = new ListNode(-1);
ListNode dummy2 = new ListNode(-1);
ListNode target = head, p = head.next;
ListNode p1 = dummy1, p2 = dummy2;
while (p != null) {
if (p.val < target.val) {
p1.next = p;
p1 = p1.next;
p = p.next;
p1.next = null;
} else {
p2.next = p;
p2 = p2.next;
p = p.next;
p2.next = null;
}
}
p1.next = target;
p1 = p1.next;
p1.next = null;
ListNode leftParted = sortInList(dummy1.next);
ListNode rightParted = sortInList(dummy2.next);
ListNode temp = leftParted;
while (temp.next != null) temp = temp.next;
temp.next = target;
target.next = rightParted;
return leftParted;
}
}
发表于 2023-08-20 02:01:59
回复(2)
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
ListNode cur=head;
//创建一个新的顺序表
ArrayList<Integer> list=new ArrayList<>();
while(cur!=null){
list.add(cur.val);
cur=cur.next;
}
Collections.sort(list);
ListNode newHead=new ListNode(-1);
ListNode p=newHead;
for(int i=0;i<list.size();i++){
p.next=new ListNode(list.get(i));
p=p.next;
}
return newHead.next;
}
}
发表于 2023-06-14 13:52:53
回复(0)
public ListNode sortInList(ListNode head) {
//把一个链表从中间拆成两个链表
if(head==null||head.next==null) return head;
ListNode fast=head;
ListNode slow=head;
ListNode slowPre=null;//注意这里是null，而不是new ListNode(0)
//找链表中点
while(fast.next!=null&&fast.next.next!=null){
fast=fast.next.next;
slow=slow.next;
slowPre=slow;//第一次的时候就已经是head.next，slow直接跳跃了head
}
//根据fast，确定中点 ***z注意这个左右中点的区分
ListNode nextHead;
nextHead=slow.next;
slow.next=null;
//合并两个有序链表
//各自排序
ListNode node1=sortInList(head);
ListNode node2=sortInList(nextHead);
ListNode dummy=new ListNode(0);
ListNode cur=dummy;
//合并
while(node1!=null&&node2!=null){
if(node1.val<node2.val){
cur.next=node1;
node1=node1.next;
cur=cur.next;
}else{
cur.next=node2;
node2=node2.next;
cur=cur.next;
}
}
while(node1!=null){
cur.next=node1;
node1=node1.next;
cur=cur.next;
}
while(node2!=null){
cur.next=node2;
node2=node2.next;
cur=cur.next;
}
return dummy.next;
}
发表于 2023-04-26 17:08:14
回复(0)
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) {
if (head == null || head.next == null) {
return head;
}
ListNode fast = head.next, slow = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode tmp = slow.next;
slow.next = null;
ListNode left = sortInList(head);
ListNode right = sortInList(tmp);
ListNode dummyHead = new ListNode(-1);
ListNode curr = dummyHead;
while (left != null && right != null) {
if (left.val < right.val) {
curr.next = left;
left = left.next;
} else {
curr.next = right;
right = right.next;
}
curr = curr.next;
}
curr.next = left != null ? left : right;
return dummyHead.next;
}
}
发表于 2023-03-21 22:56:21
回复(0)
import java.util.*;
public class Solution {
public ListNode sortInList (ListNode head) {
ArrayList<Integer> al = new ArrayList<Integer>();
ListNode p = head;
while (p != null) {
al.add(p.val);
p = p.next;
}
p = head;
Collections.sort(al);
for (int i = 0; i < al.size(); i++) {
p.val = al.get(i);
p = p.next;
}
return head;
}
}
发表于 2023-03-20 20:08:28
回复(0)
问题信息
难度：
80条回答
1423收藏
9797浏览
通过挑战的用户
查看代码-
2023-02-15 17:18:45 -
2022-10-29 12:09:13 -
2022-09-28 12:47:07 -
2022-09-27 11:13:47 -
2022-09-27 10:58:18
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
