题解 | #单链表的排序#

package main

import . "nc_tools"

/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
 *
 * @param head ListNode类 the head node
 * @return ListNode类
 */
func sortInList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	mid := head
	p := head
	for p != nil && p.Next != nil {
		p = p.Next
		if p != nil {
			p = p.Next
		}
		if p != nil {
			mid = mid.Next
		}
	}
	next := mid.Next
	mid.Next = nil
	left := sortInList(head)
	right := sortInList(next)
	p = left
	q := right
	var r *ListNode
	var root *ListNode
	for p != nil || q != nil {
		if q == nil || (p != nil && p.Val <= q.Val) {
			if r == nil {
				r = p
				root = r
			} else {
				r.Next = p
				r = r.Next
			}
			p = p.Next
			continue
		}
		if p == nil || (q != nil && p.Val > q.Val) {
			if r == nil {
				r = q
				root = r
			} else {
				r.Next = q
				r = r.Next
			}
			q = q.Next
		}
	}
	return root
	// write code here
}