使用插入排序对链表进行排序。
[编程题]链表的插入排序
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
* 需要使用插入排序，
1.创建头节点为虚节点，将虚节点指针指向原头节点
2.循环 从原头节点第二个node开始 往前 判断，是否存在比该节点大得数据，存在则交换指针，
3.每循环一次，都需要将记录下次需要遍历node得引用，
* @param head ListNode类
* @return ListNode类
*/
public ListNode insertionSortList (ListNode head) {
if(head==null||head.next==null)return head;
//创建头节点
ListNode tempNode =new ListNode(0);
//连接指针
tempNode.next=head;
//从第二个节点开始遍历是否需要插入
ListNode current =head.next;
//设置引用对象，交换指针得时候需要有 3个节点得指针变动，
//pre节点得next指向currentNode，
//currentNode得上一节点得next需要指向currentNode得next
//currentNode得next指向pre节点得next
//如果需要指针变动，则会把当前节点插入到前面，所以currentLast指针不用变动，
//如果不需要指针变动，则下次循环得时候currentLast指针为currentLast得next节点
ListNode next,pre,currentLast=head;
while (true){
pre=tempNode;
if(current==null)break;
next=current.next;
while (pre.next.val<current.val){
pre=pre.next;
}
if(pre.next!=current){
//交换 1,2,3,4,
currentLast.next = next;
current.next =pre.next;
pre.next = current;
}else{
currentLast = current;
}
current=next;
}
return tempNode.next;
}
}
发表于 2023-01-31 14:45:27
回复(0)
运行时间：337ms超过89.91% 用Java提交的代码
占用内存：17516KB超过86.54%用Java提交的代码
public ListNode insertionSortList (ListNode head) {
if(head==null) return null;if(head.next==null) return head;
// write code here
//链表进行插入和删除时，需要两个指针，一个指向父亲节点，一个指向当前节点
ListNode p1p=new ListNode(-1);
ListNode p1=p1p;
ListNode cur=null;
p1.next=head;//是比较数 待排序队列
ListNode p2p=new ListNode(-1);
ListNode p2=p2p;
p2.next=head;// 被比较数 已经排序队列
ListNode cur2=null;
// 是否进行过删除，如果有删除动作，父亲指针保持不动
boolean isDelete=false;
while(p1!=null && p1.next!=null){
cur=p1.next;
//从头开始比较
p2=p2p;
cur2=p2.next;
while((cur2)!=cur && p2!=null && cur2!=null ){
if(cur.val <= cur2.val){
//从p1链表 删除
p1.next=cur.next;
isDelete = true;
//从p2链表 插入，
p2.next=cur;
cur.next=cur2;
//
break;
}else{
p2=p2.next;
cur2=cur2.next;
}
}
//
if(isDelete){
isDelete=false;
}else{
p1=p1.next;
}
}
return p2p.next;
}
发表于 2021-09-09 19:14:28
回复(0)
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
* 找到小的节点，然后从开头遍历插入改节点
* @param head ListNode类
* @return ListNode类
*/
public ListNode insertionSortList (ListNode head) {
if (head == null || head.next == null){
return head;
}
//记录从头部节点开始进行插入后面一个较小的值，插入完成后重置执行head
ListNode p = head;
//设置哨兵节点，用于记录头部
ListNode preHead = new ListNode(0);
preHead.next = head;
//记录前一个节点
ListNode pre = head;
//比较的当前节点，从第二个开始比较
ListNode cur = head.next;
while (cur != null){
//找到小的节点
if (cur.val < pre.val){
//切分当前节点
ListNode temp = cur;
pre.next = cur.next;
cur.next = null;
cur = pre.next;
//循环从前往后插入该节点
ListNode pr = preHead;
while (p != cur){
if (temp.val < p.val){
pr.next = temp;
temp.next = p;
break;
}
p = p.next;
pr = pr.next;
}
//重置
p = preHead.next;
}else {
cur = cur.next;
pre = pre.next;
}
}
return preHead.next;
}
}
发表于 2020-09-19 16:45:36
回复(0)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode insertionSortList(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode newHead = new ListNode(0);//新建一个链表表头
ListNode cur = head.next;//原链表上的指针
//将原链表的表头即第一个节点从原链表上断开，并接到新链表上
head.next = null;
newHead.next = head;
ListNode newCur = newHead.next;//新链表上的指针
//依次取出原链表中的节点，从原链表上断开之后按顺序插入新链表上对应的位置
while(cur != null){
ListNode node = cur;//取出cur所指向的原链表中的当前节点node
cur = cur.next;//cur指针后移一位
node.next = null;//将node从原链表上断下来
if(node.val >= newCur.val){
//如果node的值比新链表尾节点（即newCur所指节点）的值大或相等，则直接插在新链表末尾即可
newCur.next = node;
newCur = newCur.next;//注意别忘了将新链表指针newCur后移一位
}else{
//如果node的值比新链表尾节点（即newCur所指节点）的值小，则从新链表首节点的下一节点开始查找第一个next节点的值比node值大的节点
ListNode p = newHead;
//依次向后遍历，直到p的值比node值小，但p.next的值比node值大时为止，这时node应该插在p节点后面
while(p.next.val<node.val){
p = p.next;
}
//把node插在p节点后面即可
node.next = p.next;
p.next = node;
}
}
//注意返回的是newHead的下一个节点才是真正的首节点
return newHead.next;
}
}
发表于 2020-03-28 22:07:20
回复(0)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode insertionSortList(ListNode head) {
if(head==null||head.next==null)
return head;
ListNode tail,nex,i,t;
tail=head;
nex=head.next;
tail.next=null;
out:
while(nex!=null){
t=nex;
nex=nex.next;
if(t.val<head.val){
t.next=head;
head=t;
}
else{
i=head;
while(i.next!=null){
if(t.val<i.next.val){
t.next=i.next;
i.next=t;
continue out;
}
i=i.next;
}
t.next=i.next;
i.next=t;
}
}
return head;
}
}
发表于 2020-02-21 14:34:47
回复(0)
public class Solution {
public ListNode insertionSortList(ListNode head) {
if (head == null || head.next == null)
return head;
// pre指向有序表的尾部节点
ListNode pre = head;
// cur指向待排序表头部的节点
ListNode cur = head.next;
// 辅助节点，用于节点插入
ListNode aux = new ListNode(-1);
aux.next = head;
while (cur != null) {
if (cur.val < pre.val) {
// 先把cur节点删除，然后再插到合适位置
pre.next = cur.next;
// l1,l2双指针，用于cur节点插入
ListNode l1 = aux;
ListNode l2 = aux.next;
//从表头往后找到l2.val大于cur.val的地方，
//把cur插到l1,l2之间
while (cur.val > l2.val) {
l1 = l2;
l2 = l2.next;
}
//把cur节点插入到l1和l2之间
l1.next = cur;
cur.next = l2;
//指向下一个待处理节点
cur = pre.next;
} else {
pre = cur;
cur = cur.next;
}
}
return aux.next;
}
}
发表于 2019-07-31 09:30:46
回复(0)
public class Solution {
public ListNode insertionSortList(ListNode head) {
if(head==null)
return head;
ListNode node1=head;
ListNode node2=head.next;
while(node1.next!=null){
while(node2!=null){
if(node1.val>node2.val){
int tem=node1.val;
node1.val=node2.val;
node2.val=tem;
}
node2=node2.next;
}
node1=node1.next;
node2=node1.next;
}
return head;
}
}
发表于 2019-03-25 20:27:49
回复(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)
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 ListNode insertionSortList(ListNode head) { if (head == null || head.next == null) { return head; } // 9->8->12->6->18，sortNode为要比较的 ListNode sortNode = head.next; ListNode tempNode = new ListNode(-1); // 要替换的前一个tempNode ListNode preNode; tempNode.next = head; // 将head的后面设置为null head.next = null; while (sortNode != null) { ListNode tempNodeCopy = tempNode.next; ListNode next = sortNode.next; preNode = tempNode; while (tempNodeCopy != null && tempNodeCopy.val <= sortNode.val) { preNode = preNode.next; tempNodeCopy = tempNodeCopy.next; } preNode.next = sortNode; sortNode.next = tempNodeCopy; sortNode = next; } return tempNode.next; }
编辑于 2018-05-15 16:11:58
回复(0)
在寻找插入位置上面花了些时间，第一次尝试将插入位置分为尾部和中间进行处理，似乎是判断次数太多，复杂度太高；
第二次改用先寻找插入位置，之后统一处理插入，顺利通过。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode insertionSortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode myHead = new ListNode(Integer.MIN_VALUE);
ListNode tmpNode = head;
while (tmpNode != null) {
ListNode indexNode = myHead;
for (; indexNode.next != null && indexNode.next.val < tmpNode.val; indexNode = indexNode.next) {
}
ListNode nextNode = tmpNode.next;
tmpNode.next = indexNode.next;
indexNode.next = tmpNode;
tmpNode = nextNode;
}
return myHead.next;
}
}
发表于 2018-04-28 11:33:43
回复(0)
public ListNode insertionSortList(ListNode head) { if(head==null || head.next==null) return head; ListNode q=head.next ; while(q!=null) { ListNode t=head; while(t!=q) { if(t.val>q.val) { int tmp=t.val; t.val=q.val; q.val=tmp; } t=t.next; } q=q.next; } return head; }
发表于 2018-04-19 16:34:18
回复(0)
/** 由于不能直接判断两个结点是否相等，因此用两个整数指标来判断每次的迭代是否到达当前有序* 队列的队尾；用结点分别记录有序部分的迭代结点前面的结点和队尾结点，方便插入操作*/public class Solution { public ListNode insertionSortList(ListNode head) { if (head == null || head.next == null) return head; //为了避免处理当前结点最小，需要更换头结点的特殊情况，//添加哑结点，值为最小整数，作为头结点 ListNode dumy = new ListNode(Integer.MIN_VALUE); dumy.next = head; ListNode first;//first表示前面有序部分的迭代结点 ListNode second;//second表示将要向前面有序部分链表插入的结点//分别记录first前面的一个节点和有序部分的尾结点ListNode beforeFirst, tmpTail; beforeFirst = dumy; tmpTail = dumy; int i, j;//用于判断first结点是否到达有序部分队尾 for (second = dumy.next, i = 1; second != null; ++ i) { for (first = dumy, j = 0; j < i; beforeFirst = first, first = first.next, ++ j) { //如果second结点值比某一个first结点值小，//则将second结点值插入beforeFirst和first结点中间，并跳出内循环 if (first.val > second.val) { tmpTail.next = second.next;//将second结点插入beforeFirst与first之间second.next = first;beforeFirst.next = second; break; } }//说明second结点值比当前有序链表中值都大，则直接添加second在有序链 if (i == j)表最后，并更新尾结点 tmpTail = second; second = tmpTail.next;//更新要插入的结点 } return dumy.next; } }
编辑于 2018-04-04 11:12:09
回复(0)
```
public class Solution {
public ListNode insertionSortList(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode node = head.next;
ListNode pNode = new ListNode(0);
pNode.next = head;
head.next = null;
while (node != null) {
ListNode posNode = pNode;
while (posNode != null) {
if (posNode.next == null || posNode.next.val >= node.val)
break;
posNode = posNode.next;
}
ListNode tmp = node;
node = node.next;
tmp.next = posNode.next;
posNode.next = tmp;
}
return pNode.next;
}
}
public ListNode insertionSortList(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode node = head.next;
ListNode pNode = new ListNode(0);
pNode.next = head;
head.next = null;
while (node != null) {
ListNode posNode = pNode;
while (posNode != null) {
if (posNode.next == null || posNode.next.val >= node.val)
break;
posNode = posNode.next;
}
ListNode tmp = node;
node = node.next;
tmp.next = posNode.next;
posNode.next = tmp;
}
return pNode.next;
}
}
```
发表于 2018-03-17 22:16:49
回复(0)
/*
手动模拟插入排序的过程啊，用h节点来遍历，temp1节点寻找插入的位置，找到后用temp2记录要插入的位置，
之后将整个链表后移到当前元素所在位置，后移的时候使用val来记录下一个节点原来的值。
*/
public ListNode insertionSortList(ListNode head) {
ListNode h = head;
while(h!=null){
ListNode temp1 = head;
while(temp1 != h && temp1.val <= h.val){
temp1 = temp1.next;
}
if(temp1!=null && temp1 != h){
ListNode temp2 = temp1;
int val = temp1.val;
while(temp1 != h){
temp1.next.val ^= val;val ^= temp1.next.val;temp1.next.val ^= val;
temp1 = temp1.next;
}
temp2.val = val;
}
h = h.next;
}
return head;
}
编辑于 2017-12-26 16:13:09
回复(0)
//使用插入排序，将一个链表进行排序
//思路：插入排序的思路是将一个数字插入到一个已经排序好的序列中，本题目中是链表
//所以我们可以新建一个链表，之后新链表中存放排序好的节点。循环遍历原链表，依次
// 在新链表中进行比较，之后进行插入操作
public class Solution {
public ListNode insertionSortList(ListNode head) {
if(head == null || head.next==null){
return head;
}
//创建一个新节点(头结点)，保存排序好的节点
ListNode sortNode = new ListNode(0);
ListNode pCur = head;
//ListNode sortHead = sortNode;
while(pCur != null){
//保存当前节点的下一个节点
ListNode nodeNext = pCur.next;
//得到排序好的链表的头指针
ListNode sortHead = sortNode;
//寻找插入位置
while(sortHead.next != null && sortHead.next.val < pCur.val){
sortHead = sortHead.next;
}
//找到位置将pCur进行插入到有序链表中
pCur.next = sortHead.next;
sortHead.next = pCur;
//更新pCur节点
pCur = nodeNext;
}
return sortNode.next;
}
}
发表于 2017-09-01 15:44:35
回复(0)
这个方法虽然比较消耗内存，但是比较好懂。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode insertionSortList(ListNode head) {
if(head == null || head.next == null) return head;
ListNode sortedList = new ListNode(0);
ListNode cur = head;
while(cur != null){
//因为cur的指向可能会改变，所以要预先存下cur的next，以备在下次循环时使用
ListNode next = cur.next;
//node代表排序数组的当前节点
//从前向后遍历排序数组的每一个节点，和当前未排序数组中的节点做比较
ListNode node = sortedList;
//初始化时假定的第一个元素是0，所以从next开始向后遍历，直到遇到值比它大的
while(node.next != null && node.next.val < cur.val){
node = node.next;
}
//交换两个节点
cur.next = node.next;
node.next = cur;
cur = next;
}
return sortedList.next;
}
}
编辑于 2017-08-03 10:52:36
回复(0)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
思路：
方法一：构建新链表，遍历原链表，插入正确的位置
方法二：插入排序,排成数组，然后用链表链接
*/
public class Solution {
public ListNode insertionSortList(ListNode head) {
if(head==null||head.next==null)
return head;
//构建新链表
ListNode root = new ListNode(0);
ListNode cur = head;//当前节点
ListNode pre = root;//前一节点
while(cur!=null)
{
//保存当前节点的下一个节点
ListNode next = cur.next;
//当前节点的前节点
pre = root;
//寻找当前节点的正确位置
while(pre.next!=null&&pre.next.val<cur.val)//如果前一节点的后一个节点不为空，且小于当前节点值，则顺移
{
pre = pre.next;
}
//将当前节点加入新链表,左移一位
cur.next = pre.next;
pre.next = cur;
//处理下一个节点
cur = next;
}
return root.next;
}
}
发表于 2017-07-29 20:43:53
回复(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群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
