148. 排序链表 Golang实现

CharlseGo / 2024-12-21 / 原文

# 题目描述：给你链表的头结点 head ，请将其按升序排列并返回排序后的链表。要求时间复杂度为O(nlogn) ## 思路分析：按要求需要使用归并排序。那么归并排序的思路是分治的思想，如下图所示：

简单说下思路：先将每次将链表划分成两个部分，直到不能划分【递归】，然后对两个链表进行排序合并。取中间点是第 876 题，合并 2 个有序链表是第 21 题。取一个链表的中间值的方法：快慢指针，每次快指针比慢指针多移动一个节点，那么当快指针到链表末尾的时候，慢指针就是到了节点的中间。合并两个链表：可以直接暴力排序，也可以使用递归调用的方法。递归调用：待补充

整体的代码：

点击查看代码

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func sortList(head *ListNode) *ListNode {
    length:=0
    curr:=head
    for curr!=nil {
        length++
        curr = curr.Next
    }
    if length<=1 {
        return head
    }
    midNode:= findMidNode(head)
    curr = midNode.Next
    midNode.Next = nil
    left:=sortList(head)
    right:=sortList(curr)
    return mergeTwoLists(left,right)
}
//leetcode submit region end(Prohibit modification and deletion)

func findMidNode(head *ListNode)*ListNode  {
    if head==nil || head.Next==nil {
        return nil
    }
    left,right := head,head
    for right.Next!=nil && right.Next.Next!=nil {
        left = left.Next
        right = right.Next.Next
    }
    return left
}

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    dummy := &ListNode{}
    current := dummy

    for list1!=nil && list2!=nil {
        if list1.Val<=list2.Val {
            current.Next = list1
            list1 = list1.Next
        }else {
            current.Next = list2
            list2 = list2.Next
        }
        current = current.Next
    }
    // 连接剩余的链表
    if list1 != nil {
        current.Next = list1
    } else {
        current.Next = list2
    }

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