一、题目简介

在O(n log n)的时间内使用常数级空间复杂度对链表进行排序。

示例1

输入：

    {30,20,40}

复制

返回值：{20,30,40}

二、解法

思路：利用归并排序，先拆分成左右两部分，然后分别排序，最后再合并。

/* 
 * 数据结构
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
  * 
  * @param head ListNode类 
  * @return ListNode类
*/
func sortList( head *ListNode ) *ListNode {
    // write code here
    if head == nil || head.Next == nil{
        return head;
    }
    
    leftList, rightList := splitList(head)
    
    return mergeList(sortList(leftList), sortList(rightList))
}

// 数组拆分成左右两部分
func splitList(head *ListNode) (*ListNode, *ListNode) {
	if head == nil {
		return nil, nil
	}
	
	// lastNode每次移动两位，middleNode每次移动一位
	// 当 lastNode 在结尾的时候，middleNode正好处于中间点位置
	lastNode := head
	var middleNode *ListNode

	for lastNode != nil {
	         //  middleNode 从nil节点开始，往后移动，所以需要先移动 middleNode
		if middleNode == nil {
			middleNode = head
		} else {
			middleNode = middleNode.Next
		}

		lastNode = lastNode.Next
		if lastNode == nil {
			break
		}

		lastNode = lastNode.Next
	}

	rightList := middleNode.Next
	middleNode.Next = nil

	return head, rightList
}

// 合并有序队列
func mergeList(a, b *ListNode) *ListNode {
	if a == nil {
		return b
	}

	if b == nil {
		return a
	}

	// 将 a队列作为基础队列,所以a的第一个数，必须是最小值
	if a.Val > b.Val {
		a, b = b, a
	}
	head := a

	for {
		if b == nil {
			break
		}

		if a.Next == nil {
			a.Next = b
			break
		}

		if a.Next.Val <= b.Val {
			a = a.Next
			continue
		}

		bNext := b.Next // 记录b下一个节点

		// 将b当前节点，插入a当前节点后面
		b.Next = a.Next
		a.Next = b

		// 将a、b链表分别往后移动一位
		a = a.Next
		b = bNext
	}

	return head
}

题目来源于牛客网