DEV Community
·
Leetcode 148：排序链表
💡
原文英文，约500词，阅读约需2分钟。
📝
内容提要
给定链表的头节点，使用归并排序方法返回排序后的链表。通过递归找到链表的中间节点，将其分为左右两部分，然后合并排序后的链表。时间复杂度为O(NlogN)，空间复杂度为O(1)。
🎯
关键要点
- 给定链表的头节点，返回排序后的链表。
- 使用归并排序方法，时间复杂度为O(NlogN)，空间复杂度为O(1)。
- 通过递归找到链表的中间节点，将链表分为左右两部分。
- 合并排序后的链表时，比较左右部分的节点值。
- 重用原链表，而不是创建新的链表来存储结果。
❓
延伸问答
如何使用归并排序对链表进行排序？
通过递归找到链表的中间节点，将链表分为左右两部分，然后合并排序后的链表。
排序链表的时间复杂度和空间复杂度是多少？
时间复杂度为O(NlogN)，空间复杂度为O(1)。
在排序链表时，如何处理原链表？
重用原链表，而不是创建新的链表来存储结果。
如何找到链表的中间节点？
使用慢指针和快指针的方法，慢指针每次移动一步，快指针每次移动两步，直到快指针到达链表末尾。
合并两个排序链表的过程是怎样的？
比较左右部分的节点值，将较小的节点连接到结果链表中，直到一个链表遍历完。
给定链表的头节点，如何返回排序后的链表？
调用排序函数，传入链表头节点，返回排序后的链表头节点。
➡️
