使用插入排序对链表进行排序。
[编程题]链表的插入排序
ListNode *insertionSortList(ListNode *head) {
if (!head)
return head;
ListNode tmp(0);
ListNode* p, *q, *t;
while (head) {
p = &tmp;
q = p->next;
t = head;
head = head->next;
while (q && q->val < t->val) {
p = p->next;
q = q->next;
}
t->next = q;
p->next = t;
}
return tmp.next;
}
//对这里面很多人表示无语，人家说插入排序， //我看排行榜里面很多人直接push节点到一个list， //sort一下，然后重新组织下链表。这些答案有何意义？ //请管理员对这些答案进行清除。
编辑于 2016-10-11 17:44:07
回复(16)
//这题不是让用插入排序吗。。。评论里怎么各式各样的。。
//解释下：
// 插入排序就是不断的向一个已经排序的列表中(此处为代码中的sortedList)添加新的节点，并且保证添加节点后的列表仍然有序。
// 一开始的时候sortedList为空，需要遍历输入链表（也就是未排序链表，此处为形参head）的每一个节点，每遍历一个，sortedList加一个。
// cur代表的就是你当前要加入sortedlist的节点。cur要插入的位置在sortedList的哪里呢？就是此处代码中node的后面。 经过这么一轮，一个节点就被加入到了sortlist。之后同理。 /**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *insertionSortList(ListNode *head) {
if(head==nullptr || head->next==nullptr) return head;
//在插入时，有可能需要在链表头插入，为了方便，新建立个链表
ListNode sortedList(0);
ListNode *cur=head;
while(cur){
//因为cur的指向可能会改变，所以要预先存下cur的next，以备在下次循环时使用
ListNode *next=cur->next;
//node代表排序数组的当前节点
//从前向后遍历排序数组的每一个节点，和当前未排序数组中的节点做比较
ListNode* node=&sortedList;
while(node->next!=nullptr && node->next->val<cur->val) //以为第一个元素是0，所以从next开始
{
node=node->next;
}
cur->next=node->next;
node->next=cur;
cur=next;
}
return sortedList.next;
}
};
编辑于 2017-05-03 23:09:06
回复(5)
// 1. 添加了个伪链表头，简化设计
// 2. 利用递归
class Solution {
public:
ListNode *insertionSortList(ListNode *head) {
if(!head || !head->next) return head;
ListNode dummyHead(0), *p;
dummyHead.next = insertionSortList(head->next);
p = &dummyHead;
while(p && p->next && head->val > p->next->val){
p = p->next;
}
head->next = p->next;
p->next = head;
return dummyHead.next;
}
};
发表于 2016-08-02 17:44:54
回复(14)
public class Solution {
public ListNode insertionSortList(ListNode head) {
if(head==null||head.next==null)
return head;
ListNode cursors = head;
ListNode tempCur = null;
ListNode temp = head;//待排序元素的上一元素
ListNode current = temp.next;//待排序的元素
while(current!=null){
if(current.val<head.val){
//排序的元素比头小 把当前元素当做头
temp.next = current.next;
current.next = head;
head = current;
}else{
// cursors-↓ ↓-temp
// 1 -> 3 -> 5 -> 8 -> 4-> 12 -> 2
//tempCur-↑ current-↑
//插入后：
// |-------有序---------|
// 1 -> 3 -> 4 -> 5 -> 8-> 12 -> 2
//找到插入的位置 current插入到cursors的前面：temp->current->cursors
tempCur = cursors;
cursors = tempCur.next;
while(cursors!=current&&cursors.val<current.val){
tempCur = cursors;
cursors = cursors.next;
}
if(cursors==current){
temp = current;
current = temp.next;
}else{
temp.next = current.next;
tempCur.next = current;
current.next = cursors;
}
}
cursors = head;
current = temp.next;
}
return head;
}
}
发表于 2016-05-30 15:35:13
回复(6)
/*思路：1.判断head和head->next是否为NULL
2.将head作为有序链表，将head->next作为待插入的链表，所以讲head和head->next分开（head->next=NULL）
3.比较大小的三种情况：（1）与头结点比较
（2）考虑pA=pA->next的情况
（3）其他
*/
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *insertionSortList(ListNode *head) {
if (head == NULL || head->next == NULL) {
return head;
}
ListNode* pB = head->next;
head->next = NULL;
ListNode *pA, *temp;
while (pB != NULL) {
pA = head;
if (pB->val < head->val) {
temp = pB->next;
//pB->next = head;
pB->next = pA;
head = pB;
pB = temp;
}
else {
while (pA->next != NULL && pA->next->val < pB->val) {
pA = pA->next;
}
temp = pB->next;
pB->next = pA->next;
pA->next = pB;
pB = temp;
}
}
return head;
}
};
发表于 2016-06-23 14:34:57
回复(0)
题目描述
Sort a linked list using insertion sort.
解题思路
解题思路就是根据插入排序的思想，每次遍历都保证前n个数都是排好序的，那么按照原生的插入排序，是从当前元素前一个元素开始一个一个往前判断，只要比前面元素小，则往前移动，一直移动到有一个元素小于它或者移动到头部了则停止，这个位置就是当前元素在这一趟中应该在的位置。但是链表中不好往前移，只能每次都从头部开始往后判断，一直找到第一个比当前元素大的元素停止，然后调整一下指针，就是让当前元素插入到本趟合适的位置。由于有可能要与第一个元素交换，所以搞一个虚拟头节点处理起来会简单一点。
代码提交
class Solution {
public ListNode insertionSortList(ListNode head) {
//1.判断一下
if(head == null || head.next == null){
return head;
}
//2.新建一个虚拟节点，后面要用
ListNode dummy = new ListNode(0);
//3.curr指向的节点及其后面所有节点都是未排序的，前面的都是排好序的
ListNode curr = head;
while(curr != null){
//4.每次循环，pre都重新指向dummy，dummy后一个节点到curr前一个节点都是排好序的
ListNode pre = dummy;
//5.保存一下当前节点后面一个节点的引用
ListNode next = curr.next;
//6.每次都从dummy节点下一个开始找，前面都是排好序的，如果小于当前节点则指针后移，一直找到pre.next为空
//或者比当前节点大的时候，停止，表明pre的下一个节点就是当前节点应该放的位置
while(pre.next != null && pre.next.val < curr.val){
pre = pre.next;
}
//7.找到当前节点应该放的位置之后，下面的工作就是移动指针，让curr插到pre和pre.next中间
//然后让curr后移一位，前面都是排好序的
curr.next = pre.next;
pre.next = curr;
curr = next;
}
//8.dummy后面就是我们所需要的用插入排序排好序的链表
return dummy.next;
}
}
编辑于 2019-03-23 20:06:51
回复(5)
class Solution {
public:
ListNode* insertionSortList(ListNode* head) {
ListNode dummy(INT_MIN);
ListNode *tail = &dummy, *curr = head;
while (curr) {
if (tail->val <= curr->val) {
tail = tail->next = curr;
curr = curr->next;
} else {
tail->next = curr->next;
ListNode* p = &dummy;
while (p->next->val < curr->val) p = p->next;
curr->next = p->next;
p->next = curr;
curr = tail->next;
}
}
return dummy.next;
}
};
发表于 2021-09-23 09:14:09
回复(0)
import java.util.*;
public class Solution {
public static ListNode insertionSortList(ListNode head) {
ListNode L=head;
ListNode SL=head;
if(head==null||head.next==null)
return head;
else{
int i=0;
ArrayList al=new ArrayList();
while(head!=null){
al.add(head.val);
head=head.next;
}
int[] a= new int[al.size()];
for(i=0;i<al.size();i++) {
a[i]=(int) al.get(i);
}
getInsertSort(a);//和上一题一样，只不过换了一个排序算法，主方法里面几乎没变。
for(i=0;i<a.length;i++) {
L.val=a[i];
L=L.next;
}
}
return SL;
} public static void getInsertSort(int[] a) {
int n = a.length;//将数组的长度赋给n是为了防止每次for循环中判断时都调用length方法影响性能
int temp;//放于for循环外面是为了防止重复创建变量
int j;
for(int i = 1; i < n;i++){//排序的趟数
temp = a[i];//赋给temp是为了防止索引i之前的元素向后移动覆盖了索引i的元素
j = i-1;
for(; j>=0&&a[j]>temp; --j) {//将大于i位置元素的元素向后移
a[j+1] = a[j];
}
a[j+1]= temp;//找到i应该在的位置，将值放置此处
}
}
}
发表于 2018-06-09 11:16:47
回复(0)
public class Solution {
public ListNode insertionSortList(ListNode head) {
if(head == null || head.next == null) return head;
ListNode r = head.next;
head.next = null;
while (r != null) {
ListNode q = head;
ListNode p = null;
while (q != null && q.val < r.val) {
p = q;
q = q.next;
}
ListNode t = r.next;
if(q == head) {
r.next = head;
head = r;
} else {
p.next = r;
r.next = q;
}
r = t;
}
return head;
}
}
编辑于 2017-03-19 15:26:11
回复(1)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *insertionSortList(ListNode *head) {
if(head==NULL)
return head;
ListNode* p=head->next;
ListNode* q=head;
ListNode* r=head;
//s=head;
while(p!=NULL){
if(p->val>=q->val){
p=p->next;
q=q->next;
}
else if(p->val<head->val){
q->next=p->next;
p->next=head;
head=p;
//p,q update
p=q->next;
}
else{
r=head;
while(r->next->val<p->val){
r=r->next;
}
q->next=p->next;
p->next=r->next;
r->next=p;
p=q->next;
}
}
return head;
}
};
发表于 2016-09-04 16:54:41
回复(0)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *insertionSortList(ListNode *head) {
ListNode *dummyHead = new ListNode(-1);
ListNode *p1 = dummyHead, *p2 = head, *prev;
while (p2 != nullptr) {
while (p1 -> next != nullptr) {
prev = p1;
p1 = p1 -> next;
if (p1 -> val > p2 -> val) {
ListNode* rest = p2 -> next;
prev -> next = p2;
p2 -> next = p1;
p2 = rest;
p1 = dummyHead;
break;
}
}
if (p1 -> next == nullptr) {
ListNode* rest = p2 -> next;
p1 -> next = p2;
p2 -> next = nullptr;
p2 = rest;
p1 = dummyHead;
}
}
return dummyHead -> next;
}
};
发表于 2020-03-10 22:07:10
回复(0)
public class Solution {
public ListNode insertionSortList(ListNode head) {
ListNode emptyNode = new ListNode(Integer.MIN_VALUE);
while(head != null){
ListNode outNextNode = head.next, innerNode = emptyNode;
while(innerNode.next != null && head.val > innerNode.next.val){
innerNode = innerNode.next;
}
head.next = innerNode.next;
innerNode.next = head;
head = outNextNode;
}
return emptyNode.next;
}
}
编辑于 2019-10-05 11:52:44
回复(1)
// 我觉得题目的本意是要求使用在原数组上进行插入排序，而不是新建链表、保存变量到容器排序后在写到原链表； //我的思路是：选中当前的结点 对比前面的所有结点（插入排序默认前面的结点都是排好序的） //如果都大于前面的结点则保持原地不动 //如果从头排序好的结点，如果出现小于本身的结点，则从链表上摘下自身节点并插入到比自己小的结点前面 //另外方便头结点的数据操作，增加了头指针辅助变量 class Solution { public: ListNode *insertionSortList(ListNode *head) { if (head == NULL) return NULL; //建立辅助头指针 ListNode * root = (ListNode *)malloc(sizeof(ListNode)); root->next = head;ListNode * current = head->next; //被比较的结点 ListNode * pre_current = head; //当前结点的前一个结点 while (current != NULL) { ListNode * temp = root->next; //类似迭代器 ListNode * pre_temp = root; //指向前一个指针 while (temp->val <= current->val && temp != current) { temp = temp->next; pre_temp = pre_temp->next; } if (temp != current) { //删除当前节点 deleteSortList(pre_current, current); //添加到合适的结点 insertSortList(pre_temp, current); current = pre_current->next; } else { //更改循环变量 current = current->next; pre_current = pre_current->next; } } head = root->next; free(root); return head; } private: ListNode *deleteSortList(ListNode *pre_ptr,ListNode *cur_ptr) { ListNode * del_ptr = cur_ptr; pre_ptr->next = del_ptr->next; return del_ptr; } void insertSortList(ListNode *pre_ptr,ListNode *add_ptr) { add_ptr->next = pre_ptr->next; pre_ptr->next = add_ptr; } };
发表于 2019-05-29 02:46:08
回复(0)
Solution 1
/*
下面是效仿数组的插入排序的一种方法。
*/
class Solution {
public:
ListNode *insertionSortList(ListNode *head) {
if(head==nullptr||head->next==nullptr)
return head;
ListNode *p,*q;
p=head->next;
while(p!=nullptr)//从第二个元素开始插入
{
q=p->next;
p->next=nullptr;//将插入元素后指针置nullptr
InsertList(head,p,q);
p=q;
}
return head;
}
private:
void InsertList(ListNode *&front,ListNode *obj,ListNode *_next)
{
ListNode *NewNode=new ListNode(obj->val);
ListNode *q,*p;
p=front;
q=front->next;
while(!(q->val==obj->val&&q->next==nullptr))//将待插指针从链表尾中删除
{
p=p->next;
q=q->next;
}
p->next=nullptr;
q=front;
if(q->val>obj->val)//当链表第一个元素大于待插元素时
{
NewNode->next=front;
front=NewNode;
while(q->next!=nullptr)
q=q->next;
q->next=_next;//将差值完成的链表与后链表接起来
}
else{
ListNode *temp;
while(q!=nullptr)
{
if(q->val<obj->val)//寻找插入位置
{
temp=q;
q=q->next;
}
else break;
}
if(q!=nullptr)//插入位置在链表中间某个位置
{
temp->next=NewNode;
NewNode->next=q;
while(q->next!=nullptr)
q=q->next;
q->next=_next;
}
else{ //插入位置在链表尾部
temp->next=NewNode;
NewNode->next=_next;
}
}
return ;
}
};
Solution 2
class Solution {
public:
ListNode *insertionSortList(ListNode *head) {
if(head==nullptr||head->next==nullptr)
return head;
ListNode *NewList=new ListNode(0);
ListNode *q,*p,*pre;
while(head!=nullptr)
{
pre=NewList;
q=pre->next;
p=head;
head=head->next;
while(q!=nullptr&&q->val<p->val)
{
pre=pre->next;
q=q->next;
}
pre->next=p;
p->next=q;
}
return NewList->next;
}
};
编辑于 2019-04-25 22:00:59
回复(0)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
/*
看了大家提交的c++代码，几乎都是用链表或者其他辅助数据结构存下所有元素，然后用现成的sort函数排序
这种方式不是本题的考察意图，虽然复杂度等因素导致这种答案也能通过测试用例，不过本题的要求是“插入排序”。
“插入排序”，简单点说，就是从混乱待排的数据中，每次选一个插入到已有序的数据中合适的位置。
所以，把xcyok同学的java代码翻译成c++的如下：
*/
class Solution {
public:
ListNode *insertionSortList(ListNode *head) {
if(head == nullptr) return head;
ListNode* dummy = new ListNode(0x80000000);//这个新链表头节点用来存已经有序的链表，val初始化为最小值
ListNode* cur = head;//从头开始处理“待排序链表”
ListNode* pre = dummy;//“已经有序链表”中的查找指针，方便找目的合适的位置
while(cur != nullptr)
{
ListNode* next = cur->next; //存下原链表中当前位置cur的下一个指针，预防断了没法继续判断
pre = dummy; //从已经有序的元素开始找.由于在已有序的链表中还是尾插，所以每次从头开始遍历
while(pre->next != nullptr && pre->next->val < cur->val)//一直找到合适的待插位置
{
pre = pre->next;
}
cur->next = pre->next;//插入合适的位置操作1
pre->next = cur;//插入合适的位置操作2
cur = next;//更新原链表中待判断的后续元素位置
}
return dummy->next;//返回链表，不包含新增的临时节点
}
};
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
/*
看了大家提交的c++代码，几乎都是用链表或者其他辅助数据结构存下所有元素，然后用现成的sort函数排序
这种方式不是本题的考察意图，虽然复杂度等因素导致这种答案也能通过测试用例，不过本题的要求是“插入排序”。
“插入排序”，简单点说，就是从混乱待排的数据中，每次选一个插入到已有序的数据中合适的位置。
所以，把xcyok同学的java代码翻译成c++的如下：
*/
class Solution {
public:
ListNode *insertionSortList(ListNode *head) {
if(head == nullptr) return head;
ListNode* dummy = new ListNode(0x80000000);//这个新链表头节点用来存已经有序的链表，val初始化为最小值
ListNode* cur = head;//从头开始处理“待排序链表”
ListNode* pre = dummy;//“已经有序链表”中的查找指针，方便找目的合适的位置
while(cur != nullptr)
{
ListNode* next = cur->next; //存下原链表中当前位置cur的下一个指针，预防断了没法继续判断
pre = dummy; //从已经有序的元素开始找.由于在已有序的链表中还是尾插，所以每次从头开始遍历
while(pre->next != nullptr && pre->next->val < cur->val)//一直找到合适的待插位置
{
pre = pre->next;
}
cur->next = pre->next;//插入合适的位置操作1
pre->next = cur;//插入合适的位置操作2
cur = next;//更新原链表中待判断的后续元素位置
}
return dummy->next;//返回链表，不包含新增的临时节点
}
};
编辑于 2019-05-14 22:25:14
回复(0)
public class Solution {
public ListNode insertionSortList(ListNode head) {
ListNode dummy = new ListNode(0);
while(head != null){
ListNode node = dummy;
while(node.next != null && node.next.val < head.val){
node = node.next;
}
ListNode tmp = head.next; //保存head的下一个节点
head.next = node.next; //拼接排序后半部分数组
node.next = head; //把前半部分排序数组和后半部分凭借
head = tmp; // 恢复head的下一个节点
}
return dummy.next;
}
}
发表于 2018-09-06 15:08:55
回复(0)
#这个题目我是完全按照插入排序来写的，思路如下：
#1.在第i次循环中，找到当前链表第i个节点到最后一个节点中中key最小的节点，将其插入第i-1个位置
#需要注意如果temp == head，head需要前进一步，否则死循环。
class Solution {
public:ListNode *insertionSortList(ListNode *head) {
if (head == NULL || head->next == NULL)
return head;
ListNode* min = new ListNode(INT16_MAX);
ListNode* runner;
ListNode* res = new ListNode(0); res->next = head;
ListNode* copy = res;
while (head->next != NULL) {
runner = head;
min = new ListNode(INT16_MAX);
min->next = head;
while (runner != NULL) {
if (runner->val < min->next->val) {
while (min->next != runner)
min = min->next;
//break;
}
runner = runner->next;
}
ListNode*temp = min->next;
if (temp == head)
head = head->next;
min->next = min->next->next;
res->next = temp;
temp->next = head;
//head = head->next;
res = temp;
}
return copy->next;
}
};
发表于 2018-08-29 01:07:33
回复(0)
//感觉自己写的太麻烦 我怎么感觉加了一个伪表头，反而麻烦了
public ListNode insertionSortList(ListNode head){
if(head==null||head.next==null)
return head;
ListNode first =new ListNode(-1);
ListNode curIndex,last,slow,fast;
first.next=head;
last=head;
curIndex=head.next;
last.next=null;
while(curIndex!=null){
//大于头节点
if(curIndex.val<=head.val){
first.next=curIndex;
curIndex=curIndex.next;
first.next.next=head;
//last=head;
head=first.next;
}
else if(curIndex.val>last.val){
last.next=curIndex;
last=last.next;
curIndex=curIndex.next;
last.next=null;
}
else{
slow=head;
fast=head.next;
while(fast.val<curIndex.val){
slow=fast;
fast=fast.next;
}
slow.next=curIndex;
curIndex=curIndex.next;
slow=slow.next;
slow.next=fast;
}
}
return first.next;
}
发表于 2017-11-17 20:35:09
回复(0)
class Solution {
public:
ListNode *insertionSortList(ListNode *head) {
if(head==NULL || head->next==NULL)
return head;
ListNode L(0),*p;
L.next = insertionSortList(head->next);
p = &L;
while(p && p->next && p->next->val < head->val)
p = p->next;
head->next = p->next;
p->next = head;
return L.next;
}
};
发表于 2017-09-07 00:59:00
回复(0)
class Solution {
public:
ListNode *insertionSortList(ListNode *head) {
if(head == nullptr || head->next == nullptr){
return head;
}
ListNode *pstart = new ListNode(0);
pstart->next = head;
head = head->next;
pstart->next->next = nullptr;
while( head ){
ListNode * temp = head;
head = head->next;
temp->next = nullptr;
ListNode *pre = pstart;
ListNode *pnext = pre->next;
while(pnext && temp->val >= pnext->val){
pre = pre->next;
pnext = pnext->next;
}
pre->next = temp;
temp->next = pnext;
}
head = pstart->next;
delete pstart;
return head;
}
};
发表于 2017-08-18 22:45:00
回复(0)
问题信息
通过挑战的用户
查看代码-
2023-03-13 10:53:28
-
2023-03-12 15:01:46
-
2023-03-08 16:08:09
-
2023-02-28 23:15:36
-
2023-02-14 16:10:53
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
