题解 | #单链表的排序#

package main
import . "nc_tools"
/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
 * 
 * @param head ListNode类 the head node
 * @return ListNode类
*/
/*
*
归并排序
step 1：首先判断链表为空或者只有一个元素，直接就是有序的。
step 2：准备三个指针，快指针right每次走两步，慢指针mid每次走一步，前序指针left每次跟在mid前一个位置。
三个指针遍历链表，当快指针到达链表尾部的时候，慢指针mid刚好走了链表的一半，正好是中间位置。
step 3：从left位置将链表断开，刚好分成两个子问题开始递归。
step 4：将子问题得到的链表合并，参考合并两个有序链表。
*/
func sortInList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	left := head
	mid := head.Next
	right := head.Next.Next
	for right != nil && right.Next != nil {
		left = left.Next
		mid = mid.Next
		right = right.Next.Next
	}
	// 断开
	left.Next = nil
	return merge(sortInList(head), sortInList(mid))
}

func merge(list1, list2 *ListNode) *ListNode {
	res := &ListNode{Val: 0}
	tmp := res
	for list1 != nil && list2 != nil {
		var newNode *ListNode
		if list1.Val < list2.Val {
			newNode = &ListNode{Val: list1.Val}
			list1 = list1.Next
		} else {
			newNode = &ListNode{Val: list2.Val}
			list2 = list2.Next
		}
		tmp.Next = newNode
		tmp = tmp.Next
	}
	if list1 != nil {
		tmp.Next = list1
	}
	if list2 != nil {
		tmp.Next = list2
	}
	return res.Next
}