148. 排序链表

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

输入: 4->2->1->3
输出: 1->2->3->4
示例 2:

输入: -1->5->3->4->0
输出: -1->0->3->4->5

思路：时间复杂度的排序算法有归并排序、堆排序、快速排序等，使用归并排序来解答。

package leetcode

//在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

//示例 1:

//输入: 4->2->1->3
//输出: 1->2->3->4
//示例 2:

//输入: -1->5->3->4->0
//输出: -1->0->3->4->5

/**
 * 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
    }
    // 找出中点链表一分为二
    p1 := head
    p2 := head.Next

    for {
        if p2 == nil {
            break
        }
        p2 = p2.Next
        if p2 == nil {
            break
        }
        p2 = p2.Next
        p1 = p1.Next
    }
    p2 = p1.Next
    p1.Next = nil
    p1 = head
    // 排序左边
    p1 = sortList(p1)
    // 排序右边
    p2 = sortList(p2)
    // 合并
    p1 = mergeTwoLists(p1, p2)
    return p1
}

func mergeTwoLists(left, right *ListNode) *ListNode {
    if left == nil {
        return right
    }
    if right == nil {
        return left
    }
    if left.Val <= right.Val {
        left.Next = mergeTwoLists(left.Next, right)
        return left
    } else {
        right.Next = mergeTwoLists(left, right.Next)
        return right
    }
}