链表的插入排序

[编程题]链表的插入排序

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

使用插入排序对链表进行排序。

示例1

输入

{30,20,40}

输出

{20,30,40}

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

算法知识视频讲解

_offer_qwq

发表于 2020-01-08 11:38:25

题目描述使用插入排序对链表进行排序。Sort a linked list using insertion sort. /** * Definition for singly-linked list. * struct ListNode { * int val; * ListN 展开全文

offer加加加加加加一

发表于 2020-09-27 19:43:56

把链表分为两部分，一部分是已经排序的链表，另一部分是还未排序的链表。每次把未排序的链表的头节点插入到已排序链表中，直到未排序链表为空为止。时间复杂度O(n^2)，空间复杂度O(1)。 ListNode* insertionSortList(ListNode* head) { if (head 展开全文

wkhuahuo

发表于 2021-10-17 21:43:26

主要确定的步骤：需要双重遍历。对于待插入的结点小于首结点情况，做处理找到对应插入的结点，进行插入。 import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * 展开全文

牛客808484225号

发表于 2022-08-08 09:47:24

public class Solution { public ListNode insertionSortList(ListNode head) { ListNode dummy = new ListNode(0); 展开全文

华科不平凡

发表于 2020-08-21 15:53:17

由于单向链表只能单方向遍历，因此不能像数组的插入排序那样。在这里使用递归实现，其有一个断链和合链的过程，这是代码的关键所在。 class Solution { public: /** * * @param head ListNode类 * @return Li 展开全文

一叶浮尘

发表于 2020-04-11 14:06:25

使用插入排序对链表进行排序。Sort a linked list using insertion sort. 这种题目其实和反转链表是很相似的。只要改变之前从后向前进行插入的模式为从前向后的插入就可以了，因为在链表上没有办法获得前向节点，之后从前往后遍历，所以这边只要转变一下思想就可以了。 /** 展开全文