148. 排序链表 (opens new window)

Description

Difficulty: 中等

Related Topics: 链表 (opens new window), 双指针 (opens new window), 分治 (opens new window), 排序 (opens new window), 归并排序 (opens new window)

给你链表的头结点 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⁵

**进阶：**你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

Solution

Language: JavaScript

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
// 终止条件
// 获取链表中间节点
// 断开链表
// 合并有序链表
var sortList = function(head) {
    if (head === null || head.next === null) {
        return head
    }

    let midNode = getMiddleNode(head)
    let rightHead = midNode.next
    midNode.next = null

    let left = sortList(head)
    let right = sortList(rightHead)

    return mergeTwoLists(left, right)
};

// 利用快慢指针找到中间节点
var getMiddleNode = function (head) {
    if (head === null || head.next === null) {
        return head
    }
    let slow = head
    let fast = head.next.next

    while (fast !== null && fast.next !== null) {
        slow = slow.next
        fast = fast.next.next
    }

    return slow
}

// 合并两个有序链表
var mergeTwoLists = function (l1, l2) {
    const dummy = new ListNode()
    let cur = dummy
    while (l1 && l2) {
        if (l1.val < l2.val) {
            [cur.next, l1] = [l1, l1.next]
        } else {
            [cur.next, l2] = [l2, l2.next]
        }
        cur = cur.next
    }
    cur.next = l1 ? l1 : l2
    return dummy.next
}