148. 排序链表

问题

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

原题链接：148. 排序链表

题解

传统的6大排序方法：

1. 插入排序
   • 简单插入排序：可以应用于链表，但需要修改比较顺序，不能从后向前比较，需要从前向后比较
   • 希尔排序：不可用于链表
2. 选择排序
   • 简单选择排序：可以应用于链表，但需要可以通过引用或指针修改节点中的值
   • 堆排序：不可用于链表
3. 交换排序
   • 冒泡排序：可以应用于链表，只影响前后两个节点
   • 快速排序：不可用于链表

特殊排序算法：

1. 归并排序：可以用于链表
2. 基数排序：不可用于链表

可见，可用于链表的排序基本上时间复杂度都为O（n^2），只有归并排序是O(nlogn)，因此最优解肯定是归并排序。

代码实现

func sortList(head *ListNode) *ListNode {
	temp := head
	length := 0
	for temp != nil {
		temp = temp.Next
		length++
	}
	if length <= 1 {
		return head
	} else {
        // 查找链表中间位置
		middle := length / 2
		l2 := head
		idx := 1
		for idx < middle {
			l2 = l2.Next
			idx++
		}
        // 将原始链表从中间分为两份，保证l1尾部指针不会导致异常，也可以通过next=nil判断处理完毕
		temp = l2
		l2 = l2.Next
		l1 := head
		temp.Next = nil
        // 归并排序 l1，l2
		l1 = sortList(l1)
		l2 = sortList(l2)
        // 对l1，l2进行merge
		return mergeListInner(l1, l2)
	}
}

// merge过程即拆出原来链表的节点，连接成一个新链表
func mergeListInner(l1, l2 *ListNode) *ListNode {
	stake := &ListNode{}
	temp := stake
	for l1 != nil && l2 != nil {
		if l1.Val < l2.Val {
			temp.Next = l1
			l1 = l1.Next
			temp = temp.Next
		} else {
			temp.Next = l2
			l2 = l2.Next
			temp = temp.Next
		}
	}
	for l1 != nil {
		temp.Next = l1
		l1 = l1.Next
		temp = temp.Next
	}
	for l2 != nil {
		temp.Next = l2
		l2 = l2.Next
		temp = temp.Next
	}
	return stake.Next
}