148.M 排序链表

Problem: 148. 排序链表

思路

链表排序的复杂度在于节点交换位置比较复杂，但是合并两个有序链表很简单，因此考虑先把链表拆成两个部分，然后分别排序，排序好之后再合并两个链表。

Code

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

    // 注意：如果fast也从head开始，在链表长度为2时，会导致左半部分的长度一直是2
	fast, slow := head.Next, head
	for fast != nil && fast.Next != nil {
		fast = fast.Next.Next
		slow = slow.Next
	}

	mid := slow.Next
	slow.Next = nil

	return mergeList(sortList(head), sortList(mid))
}

func mergeList(head1 *ListNode, head2 *ListNode) *ListNode {
	dummyHead := &ListNode{Val: -1}
	pre := dummyHead
	for head1 != nil && head2 != nil {
		if head1.Val < head2.Val {
			pre.Next = head1
			head1 = head1.Next
		} else {
			pre.Next = head2
			head2 = head2.Next
		}

		pre = pre.Next
	}

	if head1 != nil {
		pre.Next = head1
	} else {
		pre.Next = head2
	}

	return dummyHead.Next
}