目录
- 350-两个数组的交集
- 283-移动零
- 1-两数之和
- 25-K 个一组翻转链表
- 581-最短无序连续子数组
- 合并区间
- 螺旋矩阵
- 数组中相加和为0的三元组
- 数组中出现次数超过一半的数字
- 字符串出现次数的TopK问题
- 206-反转链表
- 160-相交链表
- 19-删除链表的倒数第N个节点
- 21-合并两个有序链表
- 31-下一个排列
- 链表K位翻转
- 链表排序-归并算法
- 判断链表中是否有环
- 设计LRU缓存结构
- 两个链表的第一个公共结点
- 两个链表生成相加链表
- 合并N个有序链表
- 链表内指定区间反转
链表排序-归并算法
访问量:1546
一、题目简介
在O(n log n)的时间内使用常数级空间复杂度对链表进行排序。
示例1
输入:
{30,20,40}
复制
返回值:{20,30,40}
二、解法
思路:利用归并排序,先拆分成左右两部分,然后分别排序,最后再合并。
/* * 数据结构 * type ListNode struct{ * Val int * Next *ListNode * } */ /** * * @param head ListNode类 * @return ListNode类 */ func sortList( head *ListNode ) *ListNode { // write code here if head == nil || head.Next == nil{ return head; } leftList, rightList := splitList(head) return mergeList(sortList(leftList), sortList(rightList)) } // 数组拆分成左右两部分 func splitList(head *ListNode) (*ListNode, *ListNode) { if head == nil { return nil, nil } // lastNode每次移动两位,middleNode每次移动一位 // 当 lastNode 在结尾的时候,middleNode正好处于中间点位置 lastNode := head var middleNode *ListNode for lastNode != nil { // middleNode 从nil节点开始,往后移动,所以需要先移动 middleNode if middleNode == nil { middleNode = head } else { middleNode = middleNode.Next } lastNode = lastNode.Next if lastNode == nil { break } lastNode = lastNode.Next } rightList := middleNode.Next middleNode.Next = nil return head, rightList } // 合并有序队列 func mergeList(a, b *ListNode) *ListNode { if a == nil { return b } if b == nil { return a } // 将 a队列作为基础队列,所以a的第一个数,必须是最小值 if a.Val > b.Val { a, b = b, a } head := a for { if b == nil { break } if a.Next == nil { a.Next = b break } if a.Next.Val <= b.Val { a = a.Next continue } bNext := b.Next // 记录b下一个节点 // 将b当前节点,插入a当前节点后面 b.Next = a.Next a.Next = b // 将a、b链表分别往后移动一位 a = a.Next b = bNext } return head }
题目来源于牛客网
本文为原创文章,请尊重辛勤劳动,如需转载,请保留本文地址
若您感觉本站文章不错,读后有收获,不妨赞助一下?
我要赞助