2021-03-13：手写代码：单链表快排。
福大大 答案2021-03-13：
根据链表的表头三分。比表头小的元素放左边，比表头大的元素放右边，等于表头的元素放中间。然后递归左边和递归右边。最后合并左、中、右。
代码用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} cur := head for cur != nil { fmt.Print(cur.Val, "\t") cur = cur.Next } fmt.Println() head = sortList(head) cur = head for cur != nil { fmt.Print(cur.Val, "\t") cur = cur.Next } fmt.Println()}//Definition for singly-linked list.type ListNode struct { Val int Next *ListNode}func sortList(head *ListNode) *ListNode { ret, _ := process(head) return ret}func process(head *ListNode) (*ListNode, *ListNode) { left, leftend, mid, midend, right, rightend := partition(head) if left != nil { left, leftend = process(left) } if right != nil { right, rightend = process(right) } return merge(left, leftend, mid, midend, right, rightend)}func partition(head *ListNode) (*ListNode, *ListNode, *ListNode, *ListNode, *ListNode, *ListNode) { left := &ListNode{} //虚拟节点 leftend := left mid := head midend := mid right := &ListNode{} //虚拟节点 rightend := right cur := head.Next for cur != nil { if cur.Val < mid.Val { leftend.Next = cur leftend = leftend.Next } else if cur.Val == mid.Val { midend.Next = cur midend = midend.Next } else { rightend.Next = cur rightend = rightend.Next } cur = cur.Next } leftend.Next = nil midend.Next = nil rightend.Next = nil left = left.Next if left == nil { leftend = nil } right = right.Next if right == nil { rightend = nil } return left, leftend, mid, midend, right, rightend}func merge(left, leftend, mid, midend, right, rightend *ListNode) (*ListNode, *ListNode) { head := &ListNode{} headend := head if left != nil { headend.Next = left headend = leftend } headend.Next = mid headend = midend if right != nil { headend.Next = right headend = rightend } head = head.Next if head == nil { headend = nil } return head, headend}执行结果如下：
力扣148. 排序链表
评论