对链表进行插入排序

[编程题]对链表进行插入排序

热度指数：1646 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

对链表进行插入排序，

从链表第一个元素开始可以视为部分已排序，每次操作从链表中移除一个元素，然后原地将移除的元素插入到已排好序的部分。

数据范围：链表长度满足 $1 \le n \le 1000\$ ，链表中每个元素满足 $|val| \le 10000 \$

例如输入{2,4,1}时，对应的返回值为{1,2,4}，转换过程如下图所示：

示例1

输入

{1,2,3}

输出

{1,2,3}

示例2

输入

{2,4,1}

输出

{1,2,4}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

算法知识视频讲解

小谷围做题家

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)