给定一个节点数为n的无序单链表，对其按升序排序。
数据范围：
，保证节点权值在![[-10^9,10^9]](https://www.nowcoder.com/equation?tex=%5B-10%5E9%2C10%5E9%5D)
之内。
要求：空间复杂度 )
，时间复杂度 )
[编程题]单链表的排序
自底向上的归并排序
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
class Solution {
public:
/**
*
* @param head ListNode类 the head node
* @return ListNode类
*/
pair<ListNode*, ListNode*> merge(ListNode* left, ListNode* right) {
ListNode *root=new ListNode(0);
ListNode *cur=root;
while(left!=nullptr && right!=nullptr) {
if(left->val<right->val) {
cur->next=left;
left=left->next;
} else {
cur->next=right;
right=right->next;
}
cur=cur->next;
}
if(left==nullptr) {
cur->next=right;
}else {
cur->next=left;
}
while(cur->next!=nullptr) {
cur=cur->next;
}
ListNode* head=root->next;
delete root;
return pair<ListNode*,ListNode*>{head,cur};
}
ListNode* sortInList(ListNode* head) {
if(head==nullptr || head->next==nullptr)
return head;
int len=0;
ListNode* cur=head;
while(cur!=nullptr) {
++len; //统计链表长度
cur=cur->next;
}
ListNode* root=new ListNode(0);
root->next=head;
ListNode* pre=root;
for(int step=1;step<=len;step<<=1) {//step表示每次要合并的子链表长度
pre=root;
// cout<<step<<endl;
while(pre->next!=nullptr) {
ListNode* left=pre->next;
int count=1;
cur=left;
while(cur!=nullptr && count<step) {
cur=cur->next;
++count;
}
if(cur==nullptr || cur->next==nullptr)
break;
ListNode* right=cur->next;
cur->next=nullptr;
cur=right;
count=1;
while(cur!=nullptr && count<step) {
cur=cur->next;
++count;
}
ListNode* aft=nullptr;
if(cur!=nullptr) {
aft=cur->next;
cur->next=nullptr;
}
pair<ListNode*,ListNode*> tem=merge(left,right); //合并left和right链表，同时返回首尾节点
pre->next=tem.first;
cur=tem.second;
cur->next=aft;
// while(pre!=cur) {
// cout<<pre->val<<endl;
// pre=pre->next;
// }
pre=cur;
}
}
return root->next;
}
};
发表于 2021-09-14 20:53:45
回复(0)
这个题设计的有问题，交换节点、交换值都会超时，写了一个作弊版，强迫症通知自取：
import java.util.*;
public class Solution {
public ListNode sortInList (ListNode head){
if(head == null || head.next == null)
return head;
ArrayList<Integer> space = new ArrayList<>();
for (ListNode walker = head;walker!=null;walker = walker.next)
space.add(walker.val);
space.sort(Integer::compareTo);
int i=0;
for (ListNode walker = head;walker!=null;walker = walker.next)
{
walker.val = space.get(i++);
}
return head;
}
} 交换值的版本： public ListNode sortInList_exchangeValue (ListNode head) {
if(head == null || head.next == null)
return head;
ListNode preHead = new ListNode(0);preHead.next = head;
ListNode sorted = preHead;
while (sorted.next!=null)
{
ListNode walker = sorted.next;
ListNode min = sorted.next;
while (walker != null)
{
if (walker.val<min.val)
min = walker;
walker = walker.next;
}
int tmp = sorted.next.val;
sorted.next.val = min.val;
min.val = tmp;
sorted = sorted.next;
}
return preHead.next;
} 交换节点顺序版本，用的是尾插法，属于不稳定排序： public ListNode sortInList (ListNode head) {
if(head == null || head.next == null)
return head;
ListNode resHead = new ListNode(0);
ListNode preHead = new ListNode(0);preHead.next = head;
ListNode maxPre = preHead;
ListNode maxNode = maxPre.next;
ListNode walkerPre = preHead;
ListNode walker = preHead.next;
while (preHead.next!=null)
{
while (walker!=null)
{
if (walker.val>maxNode.val)
{
maxNode = walker;
maxPre = walkerPre;
}
walkerPre = walker;
walker = walker.next;
}
maxPre.next = maxNode.next;
maxNode.next = resHead.next;
resHead.next = maxNode;
maxPre = preHead;
maxNode = maxPre.next;
walker = preHead.next;
walkerPre = preHead;
}
return resHead.next;
}
发表于 2020-11-12 15:26:15
回复(1)
链表的排序
参考大佬的代码做了一点总结
- 算法
- 虚假的选择排序：交换链表中的值
public ListNode sortInList (ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode move = head;
while (move.next != null) {
ListNode temp = move.next;
while (temp != null) {
if (temp.val < move.val) {
int val = temp.val;
temp.val = move.val;
move.val = val;
}
temp = temp.next;
}
move = move.next;
}
return head;
} - 算法
- 真正的选择排序
- 1.建立哨兵节点
- 2.每次从未排序的链表节点中找出最小的节点接到已排序链表的后面
public ListNode sortInList (ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode sorted = dummy;
while (sorted.next != null) {
ListNode pre = sorted;
ListNode cur = sorted.next;
ListNode preMin = null;
ListNode min = null;
while (cur != null) {
if (min == null || cur.val < min.val) {
preMin = pre;
min = cur;
}
pre = pre.next;
cur = cur.next;
}
preMin.next = min.next;
min.next = sorted.next;
sorted.next = min;
sorted = min;
}
return dummy.next;
} - 算法
- 归并排序
- 1.快慢指针分割链表
- 2.递归分割
- 3.合并链表
public ListNode sortInList (ListNode head) {
if (head == null || head.next == null) {
return head;
}
return mergeSort(head);
}
public ListNode mergeSort(ListNode head) {
if (head.next == null) {
return head;
}
ListNode slow = head, fast = head, pre = null;
while (fast != null && fast.next != null) {
pre = slow;
slow = slow.next;
fast = fast.next.next;
}
pre.next = null;
ListNode left = mergeSort(head);
ListNode right = mergeSort(slow);
return merge(left, right);
}
public ListNode merge(ListNode left, ListNode right) {
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
while (left != null && right != null) {
if (left.val < right.val) {
cur.next = left;
left = left.next;
} else {
cur.next = right;
right = right.next;
}
cur = cur.next;
}
if (left != null) {
cur.next = left;
}
if (right != null) {
cur.next = right;
}
return dummy.next;
}
发表于 2020-10-03 16:35:26
回复(10)
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> arr=new ArrayList<>();
while (head!=null){
arr.add(head.val);
head=head.next;
}
Collections.sort(arr);
ListNode ans=new ListNode(0);
ListNode cur=ans;
// ListNode node=ans;
for (int i=0;i<arr.size();i++){
cur.next=new ListNode(arr.get(i));
cur=cur.next;
}
return ans.next;
}
}
发表于 2021-07-15 16:17:33
回复(0)
大概思路：
1. 在链表头前边建立哨兵，开始时，已经排好序的链表为空，因此已经排序的链表的尾部指针指向刚建立的哨兵；
2. 根据选择排序的思想，我们需要每次从未排序的列表中选择最小的一个节点，利用头插法将其插入到已经排序好的链表的后面；
3. 接着，将已经排序好的链表的尾部指针指向刚插入的元素；
4. 重复步骤2和3，直到所有的元素都已经排好序，即已经排序的链表的尾部指针移动到了链表的尾部。
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) {
// 寻找最小的元素，并利用头插法插入到节点
ListNode dummy = new ListNode(Integer.MAX_VALUE);
dummy.next = head;
ListNode sorted = dummy;
while (sorted.next != null) {
ListNode pre = sorted;
ListNode cur = sorted.next;
ListNode pre_min = null;
ListNode min = null;
// 寻找最小的数
while (cur != null) {
if (min == null || cur.val < min.val) {
min = cur;
pre_min = pre;
}
// 继续向后移动指针
cur = cur.next;
pre = pre.next;
}
// 利用头插法插入
pre_min.next = min.next;
min.next = sorted.next;
sorted.next = min;
// 哨兵节点往后移动
sorted = min;
}
return dummy.next;
}
}
发表于 2020-09-28 20:21:29
回复(3)
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)
链表转数组 + 快排
void quickSorted(int *nums, int left, int right){
if (left > right) return;
int i = left, j = right, temp = nums[left];
while (i < j){
while (i < j && temp <= nums[j])
j--;
if (i < j)
nums[i++] = nums[j];
while (i < j && temp > nums[i])
i++;
nums[j--] = nums[i];
}
nums[i] = temp;
quickSorted(nums, left, i - 1);
quickSorted(nums, i + 1, right);
}
struct ListNode* sortInList(struct ListNode* head ) {
int length = 0;
struct ListNode *cur = head;
while(cur){
length++;
cur = cur->next;
}
int *nums = (int*)malloc(sizeof(int) * length);
cur = head;
int index = 0;
//链表转数组
while (cur){
nums[index++] = cur->val;
cur = cur->next;
}
quickSorted(nums, 0, length - 1);
cur = head;
int i = 0;
//数组重新转链表
while (cur){
cur->val = nums[i++];
cur = cur->next;
}
return head;
}
发表于 2021-11-12 11:16:19
回复(0)
为啥大家分的时候都要快慢指针递归二分呀，感觉好麻烦。直接按顺序每两个一组不就完事了。
class Solution {
public:
/**
*
* @param head ListNode类 the head node
* @return ListNode类
*/
//合并两个有序链表。（第一次合并链表长度为1，当然是有序的，然后之后都是有序合并）
ListNode* merge(ListNode*left,ListNode*right){
if(!left)return right;
if(!right)return left;
if(left == right)return left;
//思路是将right有序插入left中，给left设置一个头节点
unique_ptr<ListNode> dummpy(new ListNode(0));
dummpy->next = left;
ListNode*pre = dummpy.get();//left的前一节点
while(left && right){
//如果左大于右，就把右指针插入左指针左边，然后右指针右移
if(left->val > right->val){
ListNode*rightNext = right->next;
pre->next = right;
right->next = left;
pre = right;
right = rightNext;
}
//否则左指针左移
else{
pre = left;
left = left->next;
}
}
//如果right还有数据，就接到left末端。此时right的数据都大于left
if(right){
pre->next = right;
}
return dummpy->next;
}
ListNode* sortInList(ListNode* head) {
// write code here
if(!head)return head;
vector<tuple<ListNode*,ListNode*>> toSearch;
ListNode*cur = head;
ListNode*remain = nullptr;//如果链表长度为奇数，记录最后一个节点
//两个分成一组
while(cur != nullptr){
if(cur->next != nullptr){
toSearch.emplace_back(cur,cur->next);
ListNode*next = cur->next->next;
cur->next->next = nullptr;
cur->next = nullptr;
cur = next;
}
else{
remain = cur;
break;
}
}
//记录以排序的
vector<ListNode*>hasSearched;
while(true){
while(toSearch.empty() == false){
auto [left,right] = toSearch.back();
toSearch.pop_back();
//从待排序中取出一组节点，归并后放入已排序
hasSearched.emplace_back(merge(left,right));
}
//如果长度为奇数，单独的，就和已排序的最后一个合并
if(remain){
if(hasSearched.empty() == false){
hasSearched.back() = merge(hasSearched.back(), remain);
}
else{
hasSearched.emplace_back(remain);
}
remain = nullptr;
}
//如果合并玩只剩一个，就排好了
if(hasSearched.size() == 1){
break;
}
else{
toSearch.clear();
//如果奇数长，就记录最后一个为remain
if(hasSearched.size()&1){
remain = hasSearched.back();
hasSearched.pop_back();
}
//两个为一组
for(int i=0;i<hasSearched.size();i+=2){
toSearch.emplace_back(hasSearched[i],hasSearched[i+1]);
}
///清空，然后返回循环开始继续合并
hasSearched.clear();
}
}
return hasSearched.back();
}
};
编辑于 2021-03-30 23:44:32
回复(1)
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)
class Solution:
def sortInList(self , head ):
# write code here
list1=[]
cur = head
while(cur):
list1.append(cur.val)
cur=cur.next
cur = head
for i in sorted(list1):
cur.val=i
cur=cur.next
return head
def sortInList(self , head ):
# write code here
list1=[]
cur = head
while(cur):
list1.append(cur.val)
cur=cur.next
cur = head
for i in sorted(list1):
cur.val=i
cur=cur.next
return head
发表于 2022-03-11 12:43:45
回复(0)
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
class Solution {
public:
/**
*
* @param head ListNode类 the head node
* @return ListNode类
*/
static bool cmp(ListNode* a,ListNode* b){
return a->val < b->val;
}
ListNode* sortInList(ListNode* head) {
// write code here
vector<ListNode*> nums;
while(head != nullptr){
nums.push_back(head);
head = head->next;
}
sort(nums.begin(), nums.end() ,cmp);
for(int i = 0; i < nums.size(); i++){
nums[i]->next = nums[i+1];
}
nums[nums.size()-1]->next = nullptr;
return nums[0];
}
};
发表于 2021-08-22 14:12:26
回复(1)
#include <stdlib.h>
int privot(int a[], int low, int high);
void quicksort(int a[], int low, int high);
struct ListNode* sortInList(struct ListNode* head ) {
// write code here
int s[100000] = {0};
int i = 0;
struct ListNode *p = head;
//将每个节点的val存入数组s中
while (p) {
s[i++] = p->val;
p = p->next;
}
//快排
quicksort(s, 0, i-1);
p = head;
i = 0;
//重新给链表赋值val
while (p) {
p->val = s[i++];
p = p->next;
}
return head;
}
//划分
int privot(int a[], int low, int high){
int temp = a[low];
while (low < high) {
while (low < high && a[high] >= temp) high--;
a[low] = a[high];
while (low < high && a[low] <= temp) low++;
a[high] = a[low];
}
a[low] = temp;
return low;
}
//快排
void quicksort(int a[], int low, int high){
if (low < high) {
int pri = privot(a, low, high);
quicksort(a, low, pri-1);
quicksort(a, pri+1, high);
}
}
发表于 2023-03-20 13:57:28
回复(0)
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)
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
class Solution {
public:
/**
*
* @param head ListNode类 the head node
* @return ListNode类
*/
ListNode* sortInList(ListNode* head) {
// 时间复杂度O(NlogN)，空间复杂度O(logN)
if (head == NULL || head->next == NULL) return head;
ListNode* left = head, *pre = NULL, *mid = head, *right = head;
while (right && right->next) {
pre = mid;
mid = mid->next;
right = right->next->next;
}
pre->next = NULL;
return merge(sortInList(left), sortInList(mid));
}
ListNode* merge(ListNode* p1, ListNode* p2) {
ListNode* dummy = new ListNode(-1), *cur = dummy;
while (p1 && p2) {
if (p1->val < p2->val) {
cur->next = p1;
p1 = p1->next;
} else {
cur->next = p2;
p2 = p2->next;
}
cur = cur->next;
}
if (p1) cur->next = p1;
if (p2) cur->next = p2;
return dummy->next;
}
};
发表于 2022-09-29 17:53:42
回复(0)
本人不才，使用的是优先队列priority_queue,还挺方便的。
启发是之前的题目有一个题解使用的优先队列，就拿这道题练了一下手，通过了。
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
class Solution {
public:
/**
*
* @param head ListNode类 the head node
* @return ListNode类
*/
ListNode* sortInList(ListNode* head) {
// write code here
vector <int> v;
ListNode *p=head;
while (p) {
v.push_back(p->val);
p=p->next;
}
p=head;
priority_queue<int,vector<int>,greater<int>> q;//!!!priority_queue必须基于容器
for (int i=0;i<v.size();i++) {
while (p) {
q.push(p->val);
p=p->next;
}
}
p=head;javascript:void(0);
while (!q.empty()) {
p->val=q.top();
q.pop();
p=p->next;
}
return head;
}
};
发表于 2022-03-23 20:04:44
回复(0)
class Solution {
public:
ListNode* sortInList(ListNode* head) {
// 1.
vector<ListNode*> nums;
while (head) {
nums.emplace_back(head);
head = head->next;
}
// 2.
std::sort(nums.begin(), nums.end(), [](ListNode* l1, ListNode* l2) {
return l1->val <= l2->val;
});
// 3.
int n = nums.size();
for (int i = 0; i < n - 1; ++i) {
nums[i]->next = nums[i + 1];
}
nums[n - 1]->next = nullptr;
return nums[0];
}
};
发表于 2022-02-23 17:52:39
回复(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
PriorityQueue<ListNode> queue=new PriorityQueue<>((n1,n2)->n1.val-n2.val);
while(head!=null){
queue.add(head);
head=head.next;
}
ListNode pre=new ListNode(-1);
ListNode cur=pre;
while(!queue.isEmpty()){
ListNode tmp=queue.poll();
cur.next=tmp;
cur=tmp;
}
cur.next = null;
return pre.next;
}
} 自己实现的比较器，没有用collection的sort方法。但是不太明白为啥没有cur.next = null;这个不能通过，如果是用集合而不是队列来接收的话，这个指向为空是不需要的。
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<>();
while(head!=null){
list.add(head.val);
head=head.next;
}
Collections.sort(list);
ListNode cur=new ListNode(-1);
ListNode pre=cur;
for(int c:list){
ListNode tmp=new ListNode(c);
pre.next=tmp;
pre=tmp;
}
return cur.next;
}
} 就很奇怪！！！
发表于 2021-11-26 20:10:06
回复(0)
function sortInList( head ) {
// write code here
const arr = []
let cur = head
while (cur) {
arr.push(cur.val)
cur = cur.next
}
const newHead = {
next: null
}
let newCur = newHead
arr.sort((a,b) => a - b).forEach(item => {
newCur.next = {
val: item,
next: null
}
newCur = newCur.next
})
return newHead.next
}
发表于 2021-11-19 16:09:04
回复(0)
问题信息
难度：
290条回答
1298收藏
8781浏览
通过挑战的用户
查看代码-
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号
