对链表进行插入排序，
从链表第一个元素开始可以视为部分已排序，每次操作从链表中移除一个元素，然后原地将移除的元素插入到已排好序的部分。
数据范围：链表长度满足 
，链表中每个元素满足 
例如输入{2,4,1}时，对应的返回值为{1,2,4}，转换过程如下图所示：
[编程题]对链表进行插入排序
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @return ListNode类
*/
ListNode* insertionSortList(ListNode* head) {
// write code here
ListNode* p = head;
while(p->next)
{
// 去找到这个比前一个值小的结点位置
while(p->next && p->next->val > p->val)
p = p->next;
// 如果为空 则 返回
if(p->next == nullptr) return head;
// 如果不为空 则 找到异常值 位置 选择合适的位置进行插入
ListNode* tmp = new ListNode(p->next->val);
// 加入比头结点小，直接插到头结点位置
if(tmp->val < head->val)
{
tmp->next = head;
head = tmp;
}
// 否则找到合适的位置插入
else
{
// 从头结点位置开始找到合适的位置
ListNode* t = head;
// 插入的位置的值 一定是比前一个值大
while(t->next && t->next->val < tmp->val)
t = t->next;
// 插入操作
tmp->next = t->next;
t->next = tmp;
}
// 跳过被插入的位置，因为已经有序了
p->next = p->next->next;
}
return head;
}
};
发表于 2022-08-21 14:50:38
回复(0)
和数组的插入排序流程基本相同，但考虑到单链表只能向后寻找元素，因此维持的有序区域为降序，待整个链表有序后再将链表进行反转。
- 先将头节点作为有序区域的边界sortedHead，然后循环遍历后面待排序的节点waitingForSort；
- 在某次循环中，拿当前的待排序节点waitingForSort与有序区域的边界节点sortedHead（即头结点）进行比较。如果比边界节点的值小，就往后面寻找自己可以插入的点，否则就成为有序链表新的头节点；
- 当前的待排序节点完成插入后，就考虑下一个待排序节点应该插入到有序区域的位置，周而复始直到没有待排序节点；
- 最后将有序区域的链表sortedHead进行反转。
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* public ListNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @return ListNode类
*/
public ListNode insertionSortList (ListNode head) {
// write code here
if(head == null || head.next == null) return head;
ListNode sortedHead = head; // 有序部分边界(降序)
ListNode waitingForSort = head.next; // 待排序部分头结点
head.next = null; // 有序和待排序部分断开
while(waitingForSort != null){
if(waitingForSort.val >= sortedHead.val){
ListNode newHead = waitingForSort;
waitingForSort = waitingForSort.next; // 待排序的下一个节点
newHead.next = sortedHead;
sortedHead = newHead;
}else{
ListNode prev = null;
ListNode cur = sortedHead;
// 待排序部分小于有序部分的结点就不断往后换
while(cur != null && waitingForSort.val < cur.val){
prev = cur;
cur = cur.next;
}
if(cur != null){
// 中间找到了某个位置可以插入，待排序节点插入在prev和cur之间
ListNode newNode = waitingForSort;
waitingForSort = waitingForSort.next;
newNode.next = cur;
prev.next = newNode;
}else{
ListNode newTail = waitingForSort;
prev.next = newTail;
waitingForSort = waitingForSort.next;
newTail.next = null;
}
}
}
return reverseList(sortedHead);
}
private ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode cur = head;
while(cur != null){
ListNode next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
return prev;
}
}
发表于 2021-12-13 13:21:20
回复(0)
# class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param head ListNode类 # @return ListNode类 # class Solution: def insertionSortList(self , head: ListNode) -> ListNode: # write code here res = ListNode(0) point = head while point is not None: point_next = point.next insert = res while insert is not None: if insert.next is None: insert.next = point point.next = None break # 寻找插入位置 if point.val > insert.next.val: insert = insert.next continue else: tmp = insert.next insert.next = point point.next = tmp break point = point_next return res.next
发表于 2024-04-15 23:18:24
回复(0)
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @return ListNode类
*/
public ListNode insertionSortList (ListNode head) {
// write code here
ListNode dummyHead = new ListNode(-10001);
while (head != null) {
ListNode temp = head.next;
head.next = null;
insertNode(dummyHead, head);
head = temp;
}
return dummyHead.next;
}
public void insertNode(ListNode dummyHead, ListNode node) {
ListNode prev = dummyHead;
ListNode cur = dummyHead.next;
while (cur != null) {
if (node.val < cur.val) {
prev.next = node;
node.next = cur;
return;
}
prev = cur;
cur = cur.next;
}
prev.next = node;
}
}
发表于 2023-12-18 00:29:01
回复(0)
/**
* #[derive(PartialEq, Eq, Debug, Clone)]
* pub struct ListNode {
* pub val: i32,
* pub next: Option<Box<ListNode>>
* }
*
* impl ListNode {
* #[inline]
* fn new(val: i32) -> Self {
* ListNode {
* val: val,
* next: None,
* }
* }
* }
*/
struct Solution{
}
impl Solution {
fn new() -> Self {
Solution{}
}
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @return ListNode类
*/
pub fn insertionSortList(&self, head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
// write code here
// let mut ordered_num = 0;
let mut dummy_head_new = Some(Box::new(ListNode::new(233)));
let mut dummy_head = Some(ListNode::new(233));
dummy_head.as_mut()?.next = head;
// let ordered_list = None;
let mut p = &mut dummy_head;
while p.as_ref()?.next.is_some() {
let mut node = p.as_mut()?.next.take();
p.as_mut()?.next = node.as_mut()?.next.take();
let mut p_insert_next = &mut dummy_head_new;
while p_insert_next.as_ref()?.next.is_some() && p_insert_next.as_ref()?.next.as_ref()?.val <= node.as_ref()?.val {
p_insert_next = &mut p_insert_next.as_mut()?.next;
}
node.as_mut()?.next = p_insert_next.as_mut()?.next.take();
p_insert_next.as_mut()?.next = node;
}
// todo!();
dummy_head_new?.next
}
}
发表于 2023-08-18 12:14:28
回复(0)
最通俗易懂的代码
struct ListNode* insertionSortList(struct ListNode* head )
{
if(head==NULL)
return NULL;
struct ListNode *dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
dummy->next = head;
struct ListNode *p = dummy->next->next;
struct ListNode *q = dummy;
struct ListNode *cur = dummy->next;
while(p!=NULL)
{
while(q->next!=p)
{
if(q->next->val>p->val)
{
cur->next = p->next;
p->next = q->next;
q->next = p;
break;
}
q = q->next;
}
cur = p;
p = p->next;
q = dummy;
}
return dummy->next;
}
发表于 2023-04-13 20:31:36
回复(0)
package main
import "sort"
import . "nc_tools"
/*
* type ListNode struct{
* Val int
* Next *ListNode
* }
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @return ListNode类
*/
func insertionSortList( head *ListNode ) *ListNode {
arr:=[]*ListNode{}
for p:=head;p!=nil;p=p.Next{
arr=append(arr,p)
}
sort.Slice(arr,func(i,j int)bool{
return arr[i].Val<arr[j].Val
})
for i,p:=range arr{
if i+1<len(arr){
p.Next=arr[i+1]
}else{
p.Next=nil
}
}
return arr[0]
}
发表于 2023-03-07 20:23:04
回复(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类
* @return ListNode类
*/
public ListNode insertionSortList (ListNode head) {
// write code here
ListNode dummy=new ListNode(-1);
ListNode tail=dummy;
for(;head!=null;){
ListNode tmp1=head.next;
for(ListNode i=dummy;i!=null;i=i.next){
if(i.next!=null&&i.next.val>=head.val){
head.next=i.next;
i.next=head;
break;
}else if(i.next==null){
i.next=head;
tail=head;
tail.next=null;
break;
}
}
head=tmp1;
}
return dummy.next;
}
}
发表于 2023-01-24 12:21:02
回复(0)
import java.util.*;
public class Solution {
//从头插入和从中间插入和从尾部插入都是不一样的
public ListNode insertionSortList (ListNode head) {
// 设置一个pre指针
ListNode pre=head;
head=head.next;
pre.next=null;
//左边已排序的链表形成
boolean flag=true; //用于标记右边链表的当前节点是否已经插入
while(head!=null){
flag=true;
ListNode next=head.next;
head.next=null; //从链表中移除
if(head.val<=pre.val){ //从左边链表头插入
head.next=pre;
pre=head;
flag=false; //如果从头节点就已经插入，把标志赋值为flase
}
ListNode pcur=pre;
ListNode cur=pre.next; //从排序的链表头节点开始
while(flag&&cur!=null ){ //如果在中间插入，需要两个节点
if(head.val<=cur.val){
pcur.next=head;
pcur=head;
pcur.next=cur;
flag=false;
break;
}
cur=cur.next;
pcur=pcur.next;
}
//如果走到尾部依然还没有插入，就把这个节点插入尾部
if(flag){
pcur.next=head;
}
//节点插入完毕，进行下一个节点
head=next;
}
return pre;
}
}
发表于 2022-07-30 21:34:28
回复(0)
1.若head为空或只有一个节点，就直接返回 head
2.创建一个虚拟节点headNode，headNode.next = head（初始化）;方便在head前插入节点
3.创建一个节点变量cur,表示即将需要排的节点，cur = head.next(初始化)
4.创建一个节点变量lastNode，维护已经有序的链表的最后一个节点，lastNode = head(初始化)
5.如果 cur.val >= lastNode.val,有序状态，lastNode向后走一个节点
6.如果 cur.val < lastNode.val,逆序了,从虚拟节点的头向后遍历，找到cur该待在的位置
7.将 cur从链表中删了，放在其该待的位置
8.只要cur不为空，就一直执行5、6、7
2.创建一个虚拟节点headNode，headNode.next = head（初始化）;方便在head前插入节点
3.创建一个节点变量cur,表示即将需要排的节点，cur = head.next(初始化)
4.创建一个节点变量lastNode，维护已经有序的链表的最后一个节点，lastNode = head(初始化)
5.如果 cur.val >= lastNode.val,有序状态，lastNode向后走一个节点
6.如果 cur.val < lastNode.val,逆序了,从虚拟节点的头向后遍历，找到cur该待在的位置
7.将 cur从链表中删了，放在其该待的位置
8.只要cur不为空，就一直执行5、6、7
9.终于遍历完了，返回headNode.next
import java.util.*;
public class Solution {
public ListNode insertionSortList (ListNode head) {
if(head == null || head.next == null)
return head;
ListNode headNode = new ListNode(-1);
headNode.next = head;
ListNode cur = head.next;
ListNode lastNode = head;
while(cur != null) {
if(cur.val >= lastNode.val) {
lastNode = lastNode.next;
}else{
ListNode prev = headNode;
while(prev.next.val <= cur.val) {
prev = prev.next;
}
lastNode.next = cur.next;//删除cur节点
ListNode c = prev.next;
prev.next = cur;
cur.next = c;//插入节点
}
cur = lastNode.next;
}
return headNode.next;
}
}
发表于 2022-05-25 22:01:04
回复(0)
不关注底层代码逻辑，只是api的搬运工
public ListNode insertionSortList (ListNode head) {
int i=0,j=0,k=0;
ListNode p=head;
ListNode p1=head;
while(p!=null){
i++;
p=p.next;
}
int[] a=new int[i];
while(p1!=null){
a[j++]=p1.val;
p1=p1.next;
}
Arrays.sort(a);
ListNode node=head;
while(head!=null){
head.val=a[k++];
head=head.next;
}
return node;
}
发表于 2022-05-25 17:33:18
回复(0)
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @return ListNode类
*/
ListNode* insertionSortList(ListNode* head) {
// write code here
if(!head || !head->next)
return head;
typedef ListNode* list;
list node = (list)malloc(sizeof(ListNode));
node->next = head;
node->val = -99999;
list phead = head;
list p = node;//给链表增加一个头节点，以便于插入操作
list loc = nullptr;
while(phead){
p = node;
loc = phead->next;//当前节点的下一个节点，也是可能的排序元素
if(loc){
if(phead->val > loc->val){
//若当前元素大于后面一个元素，则将后一个元素插入到前面的有序序列中
list loc_min = nullptr;//插入点的前一个节点
while(p->val < loc->val){
loc_min = p;
p = p->next;
}
phead->next = loc->next;
loc->next = loc_min->next;
loc_min->next = loc;
continue;
}
}
else//后一个节点为空，则退出循环
break;
phead = phead->next;
}
return node->next;//应该是返回队头节点，而不是头节点
}
};
发表于 2022-02-10 21:45:57
回复(0)
class Solution {
public:
ListNode* insertionSortList(ListNode* head) {
// write code here
ListNode*pHead=nullptr;
ListNode*pMove=head;
ListNode*ret=new ListNode(1);
while(pMove)
{
ListNode*node=new ListNode(pMove->val);
if(!pHead)
{
pHead=node;
ret->next=pHead;
}
else if(node->val<ret->next->val)
{
node->next=ret->next;
ret->next=node;
}
else
{
ListNode*pp=ret->next;
while(pp->next)
{
if(pp->val<=node->val&&pp->next->val>node->val)break;
pp=pp->next;
}
node->next=pp->next;
pp->next=node;
}
pMove=pMove->next;
}
return ret->next;
}
};
public:
ListNode* insertionSortList(ListNode* head) {
// write code here
ListNode*pHead=nullptr;
ListNode*pMove=head;
ListNode*ret=new ListNode(1);
while(pMove)
{
ListNode*node=new ListNode(pMove->val);
if(!pHead)
{
pHead=node;
ret->next=pHead;
}
else if(node->val<ret->next->val)
{
node->next=ret->next;
ret->next=node;
}
else
{
ListNode*pp=ret->next;
while(pp->next)
{
if(pp->val<=node->val&&pp->next->val>node->val)break;
pp=pp->next;
}
node->next=pp->next;
pp->next=node;
}
pMove=pMove->next;
}
return ret->next;
}
};
发表于 2021-12-22 09:04:55
回复(0)
class Solution: def insertionSortList(self , head: ListNode) -> ListNode: # write code here if not head: return head tmp = ListNode(0) tmp.next = head pre,cur = head,head.next while cur: if pre.val<cur.val: pre,cur = cur,cur.next continue pre.next = cur.next h = tmp while h.next.val<cur.val: h = h.next t = h.next h.next = cur cur.next = t cur = pre.next return tmp.next
发表于 2021-12-21 16:41:36
回复(1)
java递归解法
import java.util.*;
public class Solution {
public ListNode insertionSortList (ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode node = insertionSortList(head.next);
ListNode p = node, pre =null;
while(p != null){
if(p.val < head.val){
pre = p;
p = p.next;
}
else{
break;
}
}
if(pre == null){
head.next = p;
return head;
}
head.next = p;
pre.next = head;
return node;
}
}
发表于 2021-12-07 15:41:13
回复(0)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
