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

示例1:

1
2
输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例2:

1
2
3

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例3:

1
2
3

输入：head = []
输出：[]

题解方法一：归并排序（递归法）

通过递归实现链表归并排序，有以下两个节点：
1、分割cut环节：找到当前链表的中点，并从中点将链表断开

  • 我们使用fast、slow快慢双指针法，奇数个节点找到中点，偶数个节点找到中心左边的节点。
  • 找到中点slow后，执行slow.next = null将链表切段。
  • 递归分割时，输入当前链表左端点head和中心节点slow的下一个节点tmp(因为链表是从slow切断的)。
  • cut递归终止条件：当head.next == None时，说明只有一个节点了，直接返回此节点。

2、合并merge环节： 将两个链表合并，转化为一个有序链表。

  • 此处不过多解释，可参考提21-缺链接

截屏2022-04-22 上午10.24.10.png

代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
var sortList = function(head) {
    if(head == null || head.next ==null) {
        return head;
    }
    let fast = head.next; slow = head; // 我们使用fast、slow快慢双指针法，奇数个节点找到中点，偶数个节点找到中心左边的节点.
    while(fast & fast.next) {
        slow = slow.next;
        fast = fast.next.next
    }
    let tmp = slow.next;
    slow.next = null;
    let left = sortList(head);
    let right = sortList(tmp);
    return merge(left, right)
};


// 此处不要用merged的递归方法，会超时
var merge = (l1, l2)=>{
    let dummyNode = new ListNode(-1)
    let prev= dummyNode
    while(l1 !== null & l2 != null){
        if (l1.val<l2.val) {
            prev.next = l1
            l1 = l1.next
        } else
        {
             prev.next = l2
            l2 = l2.next
        }
        prev = prev.next
    }
    prev.next = l1 === null ? l2: l1
    return dummyNode.next
    
    
}

总结：大功告成✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️

参考链接: