一天一道算法题（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(n²)

• 用lastNode记录已排序链表的最后一个节点，把该节点后面的节点当做待排序节点，待排序节点在排序的时候先考虑极端情况，先对比lastNode节点，如果大于等于lastNode节点，就直接放在该节点的后面，如果小于该节点，我们就从头开始遍历（一定要从dummy哨兵节点开始遍历，否则就会跳过head，如果小于head就会出错），找到合适的位置之后就可以插入了

• /**
  * Definition for singly-linked list.
  * type ListNode struct {
  * Val int
  * Next *ListNode
  * }
  */
  func sortList(head *ListNode) *ListNode {
  if head == nil || head.Next == nil {
  return head
  }

  //至少有两个节点
  dummy := &ListNode{Next : head}
  lastNode := head
  cur := head.Next

  for cur != nil {
  if cur.Val >= lastNode.Val {
  lastNode = lastNode.Next
  } else {
  //从头开始遍历查找该节点应该出现的位置
  pre := dummy
  for pre.Next.Val < cur.Val {
  pre = pre.Next
  }
  //此时pre.Next.Val >= cur.Val，所以此时的pre.Next的位置是cur应该放置的位置

  //先保存cur后面的节点放在lastNode后面
  lastNode.Next = cur.Next
  //把cur放在合适的位置
  cur.Next = pre.Next
  pre.Next = cur
  }

  cur = lastNode.Next
  }

  return dummy.Next
  }

– 归并排序

• 先来讲一下归并排序的思路

• 我们先说如果两个升序的链表合并的情况：在这种情况下，我们会使用两个指针，分别指向两个链表的最小值，然后判断谁更小，把更小的挂在哨兵节点dummy后面（就是新创建一个空节点当头节点），然后把那个已经挂在dummy的那段链表的指针向后移动一位，继续判断，就这样把两个链表合并起来。归并的思路是一开始把一段完整的链表分为两个链表，再对每一段链表继续分为两个链表，直到每一个链表只有两个节点，此时对这两个节点排序，然后返回，之后就会对两组各两个节点的链表排序，然后就会对两组各4个节点的链表排序，就这样回溯回去（不过就算左右两边长度不一样也无所谓），最后就排序好了

• 这里使用递归的方法，结束的条件是链表长度小于等于1

• /**
  * Definition for singly-linked list.
  * type ListNode struct {
  * Val int
  * Next *ListNode
  * }
  */
  func sortList(head *ListNode) *ListNode {
  if head == nil || head.Next == nil {
  return head
  }

  //快慢指针找中点
  //快指针一定要从head.Next开始查找，这样当链表长度为偶数的时候slow停在的是左边的最后一个位置，奇数是刚好在中间位置
  fast, slow := head.Next, head
  for fast != nil && fast.Next != nil {
  fast = fast.Next.Next
  slow = slow.Next
  }

  mid := slow.Next
  slow.Next = nil

  //3.递归排序左右
  l := sortList(head)
  r := sortList(mid)

  return merge(l, r)
  }

  func merge(l, r *ListNode) *ListNode {
  dummy := &ListNode{}
  cur := dummy
  //因为进入排序的链长度不一致，所以使用for循环一个一个排序，直到有一个链表排空，那剩下的链表的每一个值都比被排空链表的最大值更大，直接挂在链表最后面就行了
  for l != nil && r != nil {
  if l.Val < r.Val {
  cur.Next = l
  l = l.Next
  } else {
  cur.Next = r
  r = r.Next
  }
  cur = cur.Next
  }
  //连接剩余的链表
  if l != nil {
  cur.Next = l
  } else {
  cur.Next = r
  }

  return dummy.Next
  }

总结

本文是 《算法题目解析系列》 的第 [23] 篇，本系列将持续更新，每篇都提供清晰的思路与编程语言实现。欢迎关注，第一时间获取更新。如果你有想看的题目，也可以在评论区留言告诉我。