LeetCode_Insertion Sort List
2024-09-30 05:13:09
题目：Sort a linked list using insertion sort，即仿照插入排序（直接插入排序）对一个链表排序。
插入排序的思想：总共进行n-1趟排序，在排列第i个元素时，前面的i个元素是有序的，将第i个元素插入到前i个元素中，并且保证被插入的数组是有序的，数组是顺序存储的，因此向有序的数组插入一个元素时，需要从插入位置之后的各个元素后移。这就是插入排序的思想。插入排序的时间复杂度O（n^2），是稳定的排序方法。链表并不是顺序存储，因此，再将第i个节点插入到前i个节点，并保证有序时，需要指针的复杂运算。
要判断一次插入是否是插入到链表的最前方，因为这样会有head指针的变化。插入时，需要找到插入位置，且找到插入位置的前驱节点，找到并且找到待插节点的前驱。这个题目本身不难，但是花了好长时间，终于AC，思路值得记下来，也许到了用的上的时候就写不出来了，常看看。。。。
/**
* 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) return NULL;
if(head->next==NULL) return head;
// ListNode *p = head;
ListNode *q = head->next;
while(q!=NULL)
{
ListNode *f = head;
while(f!=q)
{
if(q->val < f->val)
{
ListNode *qf = f;
while(qf->next!=q)
{
qf = qf->next;
}//找到q的前驱节点
if(f==head)
{
head = q;
qf->next = q->next;
q->next = f;
q = qf->next;
}
else
{
ListNode *p = head;
while(p->next!=f)
{
p = p->next;
}//找到待插入节点的前驱
qf->next = q->next;
q->next = f;
p->next = q;
q = qf->next;
}
break;
}
else
{
f = f->next;
}
}
if(f==q)
q=q->next;
}
return head;
}
};
最新文章
- SQL Server时间粒度系列----第9节时间粒度示例演示
- [JS]笔记13之Date对象
- 2017年1月4日 星期三 --出埃及记 Exodus 21:30
- iOS_TCP和UDP的详解
- mysql 笔记
- 你真的了解UIView吗？
- C++使用throw抛出异常
- linux查看系统的启动时间和运行时间
- 机器人学 —— 轨迹规划（Configuration Space）
- Unit Test Generator
- Qt：无标题栏无边框程序的拖动和改变大小
- GCC编译C程序源代码
- 兼容ie\firefox\chrome的cursor
- IOS 整理
- 【WPF MaterialDesign 示例开源项目】 Work Time Manager
- python配置apache的web服务器方法（python的CGI配置）
- 阿里云配置安全组（配置入口port）
- 解决GOOGLE无法访问
- Ubuntu双网卡设置内外网上网的问题
- sqler sql 转rest api 源码解析（二） resp 协议