2021-03-16：手写代码：单链表归并排序。

福大大 答案2021-03-16：

获取链表中点，然后按中点分成两个链表。递归两个链表。合并两个链表。

代码用golang编写，代码如下：

package mainimport "fmt"func main() {    //head := &ListNode{Val: 4}    //head.Next = &ListNode{Val: 2}    //head.Next.Next = &ListNode{Val: 1}    //head.Next.Next.Next = &ListNode{Val: 3}    head := &ListNode{Val: -1}    head.Next = &ListNode{Val: 5}    head.Next.Next = &ListNode{Val: 3}    head.Next.Next.Next = &ListNode{Val: 4}    head.Next.Next.Next.Next = &ListNode{Val: 0}    printlnLinkNodeList(head)    head = MergeSort(head)    printlnLinkNodeList(head)}//Definition for singly-linked list.type ListNode struct {    Val  int    Next *ListNode}//链表打印func printlnLinkNodeList(head *ListNode) {    cur := head    for cur != nil {        fmt.Print(cur.Val, "\t")        cur = cur.Next    }    fmt.Println()}//归并排序func MergeSort(head *ListNode) *ListNode {    if head == nil || head.Next == nil {        return head    }    ret := process(head)    return ret}//递归，head不可能为空func process(head *ListNode) *ListNode {    //如果只有1个节点，直接返回    if head.Next == nil {        return head    }    //获取中点    mid := getMid(head)    midNext := mid.Next    //按中点拆分链表    mid.Next = nil    //递归    left := process(head)    right := process(midNext)    //合并    return merge(left, right)}//找中点，head一定不为空func getMid(head *ListNode) *ListNode {    fast := head    slow := head    for fast.Next != nil && fast.Next.Next != nil {        fast = fast.Next.Next        slow = slow.Next    }    return slow}//合并，left和right一定都不为空func merge(left *ListNode, right *ListNode) *ListNode {    preAns := &ListNode{}    preAnsEnd := preAns    for left != nil && right != nil {        if left.Val <= right.Val {            preAnsEnd.Next = left            left = left.Next        } else {            preAnsEnd.Next = right            right = right.Next        }        preAnsEnd = preAnsEnd.Next    }    if left == nil {        preAnsEnd.Next = right    } else {        preAnsEnd.Next = left    }    return preAns.Next}

执行结果如下：

***

[力扣148. 排序链表]()

[评论]()