Sort a linked list in O(n log n) time using constant space complexity.

一看题目，链表排序，时间复杂度 O(n log n), 直接上快排吧，链表快排

package mainimport (	"fmt")type Link struct {	next *Link	val  int}func new_list() *Link {	return &Link{next: nil}}func insert_list(list *Link, node_val int) {	head := list	pre_next := head.next	head.next = &Link{val: node_val}	head.next.next = pre_next}func show_list(list *Link) {	list_index := list.next	for list_index != nil {		fmt.Printf("%d ", list_index.val)		if list_index.next == nil {			break		}		list_index = list_index.next	}	fmt.Printf("\n")}func last_node(list *Link) *Link {	list_index := list.next	for list_index != nil {		if list_index.next == nil {			break		} else {			list_index = list_index.next		}	}	return list_index}//链表快速排序func qsort(left_node *Link, right_node *Link) {	if left_node != right_node {		middle_node := partion(left_node, right_node)		if left_node != middle_node {			qsort(left_node, middle_node)		}		if middle_node.next != nil && middle_node.next != right_node {			qsort(middle_node.next, right_node)		}	}}//由于单向链表不能找到前一个节点, 怎么找到中元值?func partion(left_node *Link, right_node *Link) *Link {	mid_val := left_node.val	left_index := left_node	right_index := right_node	lowwer_index := left_index        //小心里面节点处理出现nil指针的情况，特别小心	for left_index != right_index && left_index.next != nil {		if left_index.next.val < mid_val {			lowwer_index.val = left_index.next.val			if lowwer_index.next != nil {				left_index.next.val = lowwer_index.next.val			}			if lowwer_index.next == nil {				break			}			lowwer_index = lowwer_index.next		} else {			left_index = left_index.next		}	}	lowwer_index.val = mid_val	return lowwer_index}func main() {	list := new_list()	insert_list(list, 7)	insert_list(list, 5)	insert_list(list, 3)	insert_list(list, 13)	insert_list(list, 4)	show_list(list) // 4 13 3 5 7	first_node := list.next	last_node := last_node(list)	// 4 13 3 5 7	// 3 13 13 5 7	// 3 4 13 5 7	qsort(first_node, last_node)	show_list(list) // 3 4 5 7 13}

输出结果:

4 13 3 5 7 	3 4 5 7 13