2021-03-13：手写代码：单链表快排。

福大大架构师每日一题 · · 532 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

福大大答案2021-03-13：

根据链表的表头三分。比表头小的元素放左边，比表头大的元素放右边，等于表头的元素放中间。然后递归左边和递归右边。最后合并左、中、右。

代码用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}

    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
}

执行结果如下：