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 }
执行结果如下: