题解 | #单链表的排序#

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
	}

	// 使用快慢指针，将链表拆分成两个
	slowHead, fastHead := head, head.Next
	fast := fastHead
	slow := slowHead
	for fast != nil && fast.Next != nil {
		if fast.Next.Next != nil {
			slow.Next = slow.Next.Next
			slow = slow.Next
			fast.Next = fast.Next.Next
			fast = fast.Next
		} else if slow.Next.Next != nil {
			slow.Next = slow.Next.Next
			slow = slow.Next
			break
		} else {
			break
		}
	}
	fast.Next = nil
	slow.Next = nil
	// 对拆分的两个链表继续拆分
	slow = sortInList(slowHead)
	fast = sortInList(fastHead)
	// 对拆分排序后的链表进行合并
	return merge(slow, fast)
}

// 合并链表
func merge(head1, head2 *ListNode) *ListNode {
	res := &ListNode{
		Val: 0,
	}
	head := res
	// 合并链表
	for head1 != nil && head2 != nil {
		if head1.Val > head2.Val {
			head.Next = head2
			head2 = head2.Next
			head = head.Next
		} else {
			head.Next = head1
			head1 = head1.Next
			head = head.Next
		}
	}
	// 如果还有剩下的，也要合并
	if head1 != nil {
		head.Next = head1
	}

	if head2 != nil {
		head.Next = head2
	}
	return res.Next
}