148. 排序链表文章目录[148. 排序链表](https://leetcode.cn/problems/sort-list/)- 插入排序- 归并排序总结给你链表的头结点head请将其按升序排列并返回排序后的链表。示例 1输入head [4,2,1,3] 输出[1,2,3,4]示例 2输入head [-1,5,3,4,0] 输出[-1,0,3,4,5]示例 3输入head [] 输出[]思路- 插入排序空间复杂度O(1)时间复杂度O(n2)用lastNode记录已排序链表的最后一个节点把该节点后面的节点当做待排序节点待排序节点在排序的时候先考虑极端情况先对比lastNode节点如果大于等于lastNode节点就直接放在该节点的后面如果小于该节点我们就从头开始遍历一定要从dummy哨兵节点开始遍历否则就会跳过head如果小于head就会出错找到合适的位置之后就可以插入了/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */funcsortList(head*ListNode)*ListNode{ifheadnil||head.Nextnil{returnhead}//至少有两个节点dummy:ListNode{Next:head}lastNode:head cur:head.Nextforcur!nil{ifcur.VallastNode.Val{lastNodelastNode.Next}else{//从头开始遍历查找该节点应该出现的位置pre:dummyforpre.Next.Valcur.Val{prepre.Next}//此时pre.Next.Val cur.Val所以此时的pre.Next的位置是cur应该放置的位置//先保存cur后面的节点放在lastNode后面lastNode.Nextcur.Next//把cur放在合适的位置cur.Nextpre.Next pre.Nextcur}curlastNode.Next}returndummy.Next}- 归并排序先来讲一下归并排序的思路我们先说如果两个升序的链表合并的情况在这种情况下我们会使用两个指针分别指向两个链表的最小值然后判断谁更小把更小的挂在哨兵节点dummy后面就是新创建一个空节点当头节点然后把那个已经挂在dummy的那段链表的指针向后移动一位继续判断就这样把两个链表合并起来。归并的思路是一开始把一段完整的链表分为两个链表再对每一段链表继续分为两个链表直到每一个链表只有两个节点此时对这两个节点排序然后返回之后就会对两组各两个节点的链表排序然后就会对两组各4个节点的链表排序就这样回溯回去不过就算左右两边长度不一样也无所谓最后就排序好了这里使用递归的方法结束的条件是链表长度小于等于1/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */funcsortList(head*ListNode)*ListNode{ifheadnil||head.Nextnil{returnhead}//快慢指针找中点//快指针一定要从head.Next开始查找这样当链表长度为偶数的时候slow停在的是左边的最后一个位置奇数是刚好在中间位置fast,slow:head.Next,headforfast!nilfast.Next!nil{fastfast.Next.Next slowslow.Next}mid:slow.Next slow.Nextnil//3.递归排序左右l:sortList(head)r:sortList(mid)returnmerge(l,r)}funcmerge(l,r*ListNode)*ListNode{dummy:ListNode{}cur:dummy//因为进入排序的链长度不一致所以使用for循环一个一个排序直到有一个链表排空那剩下的链表的每一个值都比被排空链表的最大值更大直接挂在链表最后面就行了forl!nilr!nil{ifl.Valr.Val{cur.Nextl ll.Next}else{cur.Nextr rr.Next}curcur.Next}//连接剩余的链表ifl!nil{cur.Nextl}else{cur.Nextr}returndummy.Next}总结插入排序在有原本的链表有大致升序的趋势时时间复杂度可以降为O(n)但是平均时间复杂度是O(n2)空间复杂度是O(1)。在链表长度较短时哪怕无序插入排序的耗时也会更低。归并排序递归版时间复杂度是O(n logn)但是空间复杂度是O(logn)这是因为递归栈的开销。当然归并排序也可以使用迭代的方式写可以将空间复杂度降为O(1)这里就不做介绍了感兴趣的可以自行研究本文是 《算法题目解析系列》 的第 [23] 篇本系列将持续更新每篇都提供清晰的思路与编程语言实现。欢迎关注第一时间获取更新。如果你有想看的题目也可以在评论区留言告诉我。 一天一道算法题（23）：链表排序
148. 排序链表文章目录[148. 排序链表](https://leetcode.cn/problems/sort-list/)- 插入排序- 归并排序总结给你链表的头结点head请将其按升序排列并返回排序后的链表。示例 1输入head [4,2,1,3] 输出[1,2,3,4]示例 2输入head [-1,5,3,4,0] 输出[-1,0,3,4,5]示例 3输入head [] 输出[]思路- 插入排序空间复杂度O(1)时间复杂度O(n2)用lastNode记录已排序链表的最后一个节点把该节点后面的节点当做待排序节点待排序节点在排序的时候先考虑极端情况先对比lastNode节点如果大于等于lastNode节点就直接放在该节点的后面如果小于该节点我们就从头开始遍历一定要从dummy哨兵节点开始遍历否则就会跳过head如果小于head就会出错找到合适的位置之后就可以插入了/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */funcsortList(head*ListNode)*ListNode{ifheadnil||head.Nextnil{returnhead}//至少有两个节点dummy:ListNode{Next:head}lastNode:head cur:head.Nextforcur!nil{ifcur.VallastNode.Val{lastNodelastNode.Next}else{//从头开始遍历查找该节点应该出现的位置pre:dummyforpre.Next.Valcur.Val{prepre.Next}//此时pre.Next.Val cur.Val所以此时的pre.Next的位置是cur应该放置的位置//先保存cur后面的节点放在lastNode后面lastNode.Nextcur.Next//把cur放在合适的位置cur.Nextpre.Next pre.Nextcur}curlastNode.Next}returndummy.Next}- 归并排序先来讲一下归并排序的思路我们先说如果两个升序的链表合并的情况在这种情况下我们会使用两个指针分别指向两个链表的最小值然后判断谁更小把更小的挂在哨兵节点dummy后面就是新创建一个空节点当头节点然后把那个已经挂在dummy的那段链表的指针向后移动一位继续判断就这样把两个链表合并起来。归并的思路是一开始把一段完整的链表分为两个链表再对每一段链表继续分为两个链表直到每一个链表只有两个节点此时对这两个节点排序然后返回之后就会对两组各两个节点的链表排序然后就会对两组各4个节点的链表排序就这样回溯回去不过就算左右两边长度不一样也无所谓最后就排序好了这里使用递归的方法结束的条件是链表长度小于等于1/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */funcsortList(head*ListNode)*ListNode{ifheadnil||head.Nextnil{returnhead}//快慢指针找中点//快指针一定要从head.Next开始查找这样当链表长度为偶数的时候slow停在的是左边的最后一个位置奇数是刚好在中间位置fast,slow:head.Next,headforfast!nilfast.Next!nil{fastfast.Next.Next slowslow.Next}mid:slow.Next slow.Nextnil//3.递归排序左右l:sortList(head)r:sortList(mid)returnmerge(l,r)}funcmerge(l,r*ListNode)*ListNode{dummy:ListNode{}cur:dummy//因为进入排序的链长度不一致所以使用for循环一个一个排序直到有一个链表排空那剩下的链表的每一个值都比被排空链表的最大值更大直接挂在链表最后面就行了forl!nilr!nil{ifl.Valr.Val{cur.Nextl ll.Next}else{cur.Nextr rr.Next}curcur.Next}//连接剩余的链表ifl!nil{cur.Nextl}else{cur.Nextr}returndummy.Next}总结插入排序在有原本的链表有大致升序的趋势时时间复杂度可以降为O(n)但是平均时间复杂度是O(n2)空间复杂度是O(1)。在链表长度较短时哪怕无序插入排序的耗时也会更低。归并排序递归版时间复杂度是O(n logn)但是空间复杂度是O(logn)这是因为递归栈的开销。当然归并排序也可以使用迭代的方式写可以将空间复杂度降为O(1)这里就不做介绍了感兴趣的可以自行研究本文是 《算法题目解析系列》 的第 [23] 篇本系列将持续更新每篇都提供清晰的思路与编程语言实现。欢迎关注第一时间获取更新。如果你有想看的题目也可以在评论区留言告诉我。