148. 排序链表

题目

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

难度：🌟🌟🌟

示例 1：

输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：

输入：head = []
输出：[]

提示：

• 链表中节点的数目在范围 [0, 5 * 10⁴] 内
• -10⁵ <= Node.val <= 10⁵

题解

参考：Sort List——经典（链表中的归并排序） https://www.cnblogs.com/qiaozhoulin/p/4585401.html
利用归并的思想，递归地将当前链表分为两段，然后 merge，分两段的方法是使用 fast-slow 法，用两个指针，一个每次走两步，一个走一步，直到快的走到了末尾，然后慢的所在位置就是中间位置，这样就分成了两段。

代码实现

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func sortList(head *ListNode) *ListNode {
	return mergeSort(head)
}

func mergeSort(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	slow, fast := head, head
	var half *ListNode
	for fast != nil && fast.Next != nil {
		half = slow
		slow = slow.Next
		fast = fast.Next.Next
	}
	half.Next = nil
	left := mergeSort(head)
	right := mergeSort(slow)
	return merge(left, right)
}

func merge(left, right *ListNode) *ListNode {
	dummyHead := &ListNode{Val: -1}
	p := dummyHead
	for left != nil && right != nil {
		if left.Val < right.Val {
			p.Next = left
			left = left.Next
		} else {
			p.Next = right
			right = right.Next
		}
		p = p.Next
	}
	if left != nil {
		p.Next = left
	}
	if right != nil {
		p.Next = right
	}
	return dummyHead.Next
}