给定一个节点数为n的无序单链表，对其按升序排序。
数据范围：
，保证节点权值在![[-10^9,10^9]](https://www.nowcoder.com/equation?tex=%5B-10%5E9%2C10%5E9%5D)
之内。
要求：空间复杂度 )
，时间复杂度 )
[编程题]单链表的排序
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)
public class Solution {
public ListNode sortInList (ListNode head) {
// write code here
if (head == null) return head;
List<Integer> list = new ArrayList();
while (head != null) {
list.add(head.val);
head = head.next;
}
Collections.sort(list);
ListNode sentinel = new ListNode(-1);
ListNode cur = sentinel;
for (int i = 0; i < list.size(); i++) {
cur.next = new ListNode(list.get(i));
cur = cur.next;
}
return sentinel.next;
}
}
发表于 2023-03-18 09:17:09
回复(0)
public ListNode sortInList (ListNode head) {
// write code here
ListNode a = head;
int count1 = 0;
//计算链表大小赋值给数组
while (a != null){
count1++;
a = a.next;
}
int [] number = new int[count1];
int count2 = 0;
ListNode cur = head;
ListNode tmp = head;
while (cur != null){
number[count2] = cur.val;
cur = cur.next;
count2++;
}
Arrays.sort(number);
for(int i = 0; i<count2; i++){
tmp.val = number[i];
tmp = tmp.next;
}
return head;
}
发表于 2023-02-09 12:21:06
回复(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) {
// write code here
// 递归推出条件：如果当前节点为空或者后面没有节点了，返回节点
if(head == null || head.next == null) return head;
ListNode quick = head.next;
ListNode slow = head;
while(true){
if(quick == null || quick.next == null) break;
quick = quick.next.next;
slow = slow.next;
}
// 从中间切割链表
ListNode temp = slow.next;
slow.next = null;
// 左右两边分别递归
ListNode left = sortInList(head);
ListNode right = sortInList(temp);
ListNode pre = new ListNode(0);
ListNode cur = pre;
// 排序操作
while(left != null && right != null){
if(left.val < right.val){
pre.next = left;
left = left.next;
}else{
pre.next = right;
right = right.next;
}
pre = pre.next;
}
pre.next = left == null ? right : left;
return cur.next;
}
}
发表于 2023-01-11 21:29:39
回复(1)
public ListNode sortInList (ListNode head) {
// write code here
ListNode cur=head;
List<Integer> list=new ArrayList<>();
while(cur!=null){
list.add(cur.val);
cur=cur.next;
}
Collections.sort(list);
ListNode fake=new ListNode(1);
ListNode last=fake;
for(int i=0;i<list.size();i++){
ListNode node=new ListNode(list.get(i));
last.next=node;
last=node;
}
return fake.next;
}
发表于 2022-12-18 14:19:17
回复(0)
public ListNode sortInList (ListNode head) {
// write code here
PriorityQueue<ListNode> queue = new PriorityQueue<>(new Comparator<ListNode>(){
@Override
public int compare(ListNode l1 ,ListNode l2){
return l1.val-l2.val;
}
});
while(head!=null){
queue.add(head);
head=head.next;
}
ListNode pre = new ListNode(0),p1=pre;
while(!queue.isEmpty()){
p1.next=queue.poll();
p1=p1.next;
}
p1.next=null;
return pre.next;
}
发表于 2022-11-25 22:43:55
回复(0)
//使用最小优队列实现
public ListNode sortInList (ListNode head) {
Queue<ListNode> pQueue = new PriorityQueue<>((v1, v2)-> v1.val - v2.val);
ListNode pre = new ListNode(0);
ListNode res = pre;
while (head != null) {
pQueue.add(head);
head = head.next;
}
while (!pQueue.isEmpty()) {
ListNode node = pQueue.poll();
node.next = null;
pre.next = node;
pre = pre.next;
}
return res.next;
}
发表于 2022-11-22 19:08:39
回复(0)
问题信息
难度：
74条回答
1306收藏
8833浏览
通过挑战的用户
查看代码-
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群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
