2021-03-16：手写代码：单链表归并排序。
福大大 答案2021-03-16：
获取链表中点，然后按中点分成两个链表。递归两个链表。合并两个链表。
代码用golang编写，代码如下：
package main
import "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
}执行结果如下：