leetcode 刷题之路 27 Insertion Sort List

2024-08-29 17:32

本文主要是介绍leetcode 刷题之路 27 Insertion Sort List,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Sort a linked list using insertion sort.

利用插入排序对一个链表进行排序。

插入排序是将待排序的序列分为部分,分别为有序的部分和无序的部分,排序时每次从无序的部分取出一个元素插入到有序的部分中合适的位置,初始时,有序部分只有一个元素,该元素自有序。根据这个思想,并为了方便起见,我们创建一个头结点dummyHead存储排序后的链表,初始阶段,该链表中只存储无序链表中的第一个元素。随后我们依次从原链表中取出元素加入到该有序链表中合适的位置,使得插入后链表始终有序,直到原链表空,排序结束。 

测试通过程序:

/*** 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* dummyHead = new ListNode(0);  //创建一个辅助的头结点,存储排序后的链表dummyHead->next = head;					//和数组的插入排序一样,第一个节点自有序head = head->next;dummyHead->next->next = NULL;ListNode *p;ListNode *q;while (head != NULL)			{p = head;head = head->next;q = dummyHead;while (q->next != NULL)				//依次将无序链表的节点插入到有序链表中{if (q->next->val <= p->val)		//=保证稳定性q = q->next;elsebreak;}p->next = q->next;q->next = p;}p = dummyHead->next;delete dummyHead;return p;}
};


这篇关于leetcode 刷题之路 27 Insertion Sort List的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1118502

相关文章

C#之List集合去重复对象的实现方法

《C#之List集合去重复对象的实现方法》:本文主要介绍C#之List集合去重复对象的实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C# List集合去重复对象方法1、测试数据2、测试数据3、知识点补充总结C# List集合去重复对象方法1、测试数据

Python中合并列表(list)的六种方法小结

《Python中合并列表(list)的六种方法小结》本文主要介绍了Python中合并列表(list)的六种方法小结,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋... 目录一、直接用 + 合并列表二、用 extend() js方法三、用 zip() 函数交叉合并四、用

Java List排序实例代码详解

《JavaList排序实例代码详解》:本文主要介绍JavaList排序的相关资料,Java排序方法包括自然排序、自定义排序、Lambda简化及多条件排序,实现灵活且代码简洁,文中通过代码介绍的... 目录一、自然排序二、自定义排序规则三、使用 Lambda 表达式简化 Comparator四、多条件排序五、

Java使用Stream流的Lambda语法进行List转Map的操作方式

《Java使用Stream流的Lambda语法进行List转Map的操作方式》:本文主要介绍Java使用Stream流的Lambda语法进行List转Map的操作方式,具有很好的参考价值,希望对大... 目录背景Stream流的Lambda语法应用实例1、定义要操作的UserDto2、ListChina编程转成M

C++ Sort函数使用场景分析

《C++Sort函数使用场景分析》sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变,如果某些场景需要保持相同元素间的相对顺序,可使... 目录C++ Sort函数详解一、sort函数调用的两种方式二、sort函数使用场景三、sort函数排序

Java中List的contains()方法的使用小结

《Java中List的contains()方法的使用小结》List的contains()方法用于检查列表中是否包含指定的元素,借助equals()方法进行判断,下面就来介绍Java中List的c... 目录详细展开1. 方法签名2. 工作原理3. 使用示例4. 注意事项总结结论:List 的 contain

java streamfilter list 过滤的实现

《javastreamfilterlist过滤的实现》JavaStreamAPI中的filter方法是过滤List集合中元素的一个强大工具,可以轻松地根据自定义条件筛选出符合要求的元素,本文就来... 目录1. 创建一个示例List2. 使用Stream的filter方法进行过滤3. 自定义过滤条件1. 定

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

python中列表list切分的实现

《python中列表list切分的实现》列表是Python中最常用的数据结构之一,经常需要对列表进行切分操作,本文主要介绍了python中列表list切分的实现,文中通过示例代码介绍的非常详细,对大家... 目录一、列表切片的基本用法1.1 基本切片操作1.2 切片的负索引1.3 切片的省略二、列表切分的高

java两个List的交集,并集方式

《java两个List的交集,并集方式》文章主要介绍了Java中两个List的交集和并集的处理方法,推荐使用Apache的CollectionUtils工具类,因为它简单且不会改变原有集合,同时,文章... 目录Java两个List的交集,并集方法一方法二方法三总结java两个List的交集,并集方法一