LeetCode-热题100：148. 排序链表

题目描述

给你链表的头结点 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 = []
输出： []

提示：

• 链表中节点的数目在范围 [0, 5 * 10⁴] 内
• -10⁵ <= Node.val <= 10⁵

代码及注释

/**
 * 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
    }

    // 使用快慢指针找到链表的中点
    slow, fast := head, head
    var cur *ListNode
    for fast != nil && fast.Next != nil {
        cur = slow
        slow = slow.Next
        fast = fast.Next.Next
    }

    // 断开链表，将链表分为两部分
    cur.Next = nil

    // 递归地对左右两部分进行排序
    l := sortList(head)
    r := sortList(slow)

    // 合并两个有序链表
    return merge(l, r)
}

func merge(l1 *ListNode, l2 *ListNode) *ListNode {
    // 使用哑节点简化代码
    var dummy = &ListNode{}
    cur := dummy

    // 循环比较两个链表的节点，并将较小的节点连接到新链表中
    for l1 != nil && l2 != nil {
        if l1.Val > l2.Val {
            cur.Next = l2
            l2 = l2.Next
        } else {
            cur.Next = l1
            l1 = l1.Next
        }
        cur = cur.Next
    }

    // 将剩余的节点连接到新链表的末尾
    if l1 != nil {
        cur.Next = l1
    } else {
        cur.Next = l2
    }

    // 返回合并后的链表
    return dummy.Next
}

代码解释

sortList 函数

1. 终止条件：

   if head == nil || head.Next == nil {
       return head
   }
   

   当链表为空或只有一个节点时，无需排序，直接返回。

2. 找到中点：

   slow, fast := head, head
   var cur *ListNode
   for fast != nil && fast.Next != nil {
       cur = slow
       slow = slow.Next
       fast = fast.Next.Next
   }
   cur.Next = nil
   

   使用快慢指针找到链表的中点，并将链表断开，得到两个子链表 l 和 r。

3. 递归排序：

   l := sortList(head)
   r := sortList(slow)
   

   使用递归对左右两个子链表进行排序。

4. 合并两个排序后的子链表：

   return merge(l, r)
   

   调用 merge 函数合并两个排序后的子链表。

merge 函数

1. 初始化：

   var dummy = &ListNode{}
   cur := dummy
   

   使用哑节点 dummy 和 cur 指针来合并两个链表。

2. 比较合并：

   for l1 != nil && l2 != nil {
       if l1.Val > l2.Val {
           cur.Next = l2
           l2 = l2.Next
       } else {
           cur.Next = l1
           l1 = l1.Next
       }
       cur = cur.Next
   }
   

   比较 l1 和 l2 的当前节点值，将较小的节点连接到 cur.Next。

3. 处理剩余节点：

   if l1 != nil {
       cur.Next = l1
   } else {
       cur.Next = l2
   }
   

   将剩余的 l1 或 l2 链接到 cur.Next。