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. 排序連結串列](https://leetcode-cn.com/problems/sort-list/)