1
/**
2
 * Definition for singly-linked list.
3
 * function ListNode(val, next) {
4
 *     this.val = (val===undefined ? 0 : val)
5
 *     this.next = (next===undefined ? null : next)
6
 * }
7
 */
8
/**
9
 * @param {ListNode} head
10
 * @return {ListNode}
11
 */
12
var sortList = function (head) {
13

14
    const toSortList = (head, tail) => {
15

16
        if (!head) return head;
17
        if (head.next === tail) {
18
            head.next = null;
19
            return head;
20
        }
21

22
        let fast = slow = head;
23

24

25
        while (fast !== tail) {
26
            slow = slow.next;
27
            fast = fast.next;
28
            if (fast !== tail) {
29
                fast = fast.next;
30
            }
31
        }
32

33
        let mid = slow;
34
        return merge(toSortList(head, mid), toSortList(mid, tail))
35
    }
36

37
    const merge = (head1, head2) => {
38
        const dummyHead = new ListNode(0);
39
        let temp = dummyHead, temp1 = head1, temp2 = head2;
40

41
        while (temp1 !== null && temp2 !== null) {
42
            if (temp1.val <= temp2.val) {
43
                temp.next = temp1;
44
                temp1 = temp1.next
45
            } else {
46
                temp.next = temp2;
47
                temp2 = temp2.next
48
            }
49

50
            temp = temp.next;
51
        }
52

53
        if (temp1 !== null) {
54
            temp.next = temp1
55
        } else if (temp2 !== null) {
56
            temp.next = temp2;
57
        }
58

59
        return dummyHead.next;
60
    }
61

62

63
    return toSortList(head, null);
64
};

1
/**
2
 * Definition for singly-linked list.
3
 * function ListNode(val, next) {
4
 *     this.val = (val===undefined ? 0 : val)
5
 *     this.next = (next===undefined ? null : next)
6
 * }
7
 */
8
/**
9
 * @param {ListNode} head
10
 * @return {ListNode}
11
 */
12
const sortList = (head) => {
13
    // 边界处理
14
    if (!head || !head.next) return head;
15

16
    // 获取链表长度
17
    let n = 0, cur = head;
18
    while (cur) {
19
        n++;
20
        cur = cur.next;
21
    }
22

23
    const dummy = new ListNode(-1, head);
24

25
    // 子链表长度从1开始倍增
26
    for (let size = 1; size < n; size *= 2) {
27
        let prev = dummy;
28
        let cur = dummy.next;
29

30
        while (cur) {
31
            // 获取左子链表
32
            const left = cur;
33
            const right = split(left, size);
34
            cur = split(right, size); // 剩余部分
35

36
            // 合并左右子链表
37
            prev.next = merge(left, right);
38

39
            // 移动prev到合并后链表的末尾
40
            while (prev.next) {
41
                prev = prev.next;
42
            }
43
        }
44
    }
45

46
    return dummy.next;
47
};
48

49
// 合并两个有序链表
50
const merge = (l1, l2) => {
51
    const dummy = new ListNode(-1);
52
    let cur = dummy;
53

54
    while (l1 && l2) {
55
        if (l1.val <= l2.val) {
56
            cur.next = l1;
57
            l1 = l1.next;
58
        } else {
59
            cur.next = l2;
60
            l2 = l2.next;
61
        }
62
        cur = cur.next;
63
    }
64

65
    cur.next = l1 || l2;
66
    return dummy.next;
67
};
68

69
// 分割链表：返回后半部分头节点
70
const split = (head, size) => {
71
    if (!head) return null;
72

73
    // 移动size-1步找到分割点
74
    for (let i = 1; i < size && head.next; i++) {
75
        head = head.next;
76
    }
77

78
    const nextHead = head.next;
79
    head.next = null; // 断开连接
80
    return nextHead;
81
};