目录
- 350-两个数组的交集
- 283-移动零
- 1-两数之和
- 25-K 个一组翻转链表
- 581-最短无序连续子数组
- 合并区间
- 螺旋矩阵
- 数组中相加和为0的三元组
- 数组中出现次数超过一半的数字
- 字符串出现次数的TopK问题
- 206-反转链表
- 160-相交链表
- 19-删除链表的倒数第N个节点
- 21-合并两个有序链表
- 31-下一个排列
- 链表K位翻转
- 链表排序-归并算法
- 判断链表中是否有环
- 设计LRU缓存结构
- 两个链表的第一个公共结点
- 两个链表生成相加链表
- 合并N个有序链表
- 链表内指定区间反转
插入排序-链表
访问量:1679
一、简介
单链表的插入排序
输入:
{30,20,40}
返回值:
{20,30,40}
二、解法
思路:利用插入排序,如下:
func insertionSortList(head *ListNode) *ListNode { // write code here if head == nil || head.Next == nil { return head } p := head // 每次将 p.Next插入队列 for p.Next != nil { // 端口 p.next 节点 node := p.Next // 将当前节点作为新的列表头节点 if node.Val < head.Val { p.Next = p.Next.Next node.Next = head head = node continue } // 找出node 应该在的位置 p1 := head p2 := p1.Next for p2 != node { if p2.Val > node.Val { break } p1 = p1.Next p2 = p2.Next } // 将node 插入 p1, 和 p2之间 if p2 != node { p.Next = p.Next.Next p1.Next = node node.Next = p2 continue } // 不需要移动,接着判断链表下个节点 p = p.Next } return head }
题目来源于牛客网
本文为原创文章,请尊重辛勤劳动,如需转载,请保留本文地址
若您感觉本站文章不错,读后有收获,不妨赞助一下?
我要赞助