剑指 Offer II 077. 链表排序

给定链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

示例 1：

img

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

示例 2：

img

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

示例 3：

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

提示：

  • 链表中节点的数目在范围 [0, 5 * 104] 内
  • -105 <= Node.val <= 105

解法1：借助数组

流程：
  1. 遍历链表将链表中的元素存入数组
  2. 对数组排序
  3. 再次遍历链表和数组，将排好序的元素存入链表中
代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public ListNode sortList(ListNode head) {
    //辅助数组
    ArrayList<Integer> list = new ArrayList<>();
    ListNode cur = head;
    //遍历链表，把各个节点的值存入数组
    while(cur != null){
        list.add(cur.val);
        cur = cur.next;
    }
    //数组排序
    Collections.sort(list);
    cur = head;
    //重新赋值
    for(int i = 0;i < list.size();i++){
        cur.val = list.get(i);
        cur = cur.next;
    }
    return head;

}

解法2：归并排序

流程：
  1. 通过快慢指针找到当前链表的中心节点，在此处将链表断开
  2. 递归对两边链表进行排序
  3. 归并合并两个有序链表(合并两个有序链表)
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
38
39
40
41
42
43
44
45
46
47
48
public ListNode sortList(ListNode head) {
      //递归中止条件
    if(head == null || head.next == null){
        return head;// write code here
}
    
    //快慢指针,这里将快指针调快一个是为了使慢指针能位于中心节点或中心节点前一节点，方便断链
    ListNode fast = head.next;
    ListNode slow = head;
    
    
    //快慢指针找出链表中心
    while(fast != null && fast.next != null){
        slow = slow.next;
        fast = fast.next.next;
    }
    
    //标识后半条链
    ListNode temp = slow.next;
    
    //断链
    slow.next = null;
    
    //递归对两条子链进行排序
    ListNode left = sortList(head);
    ListNode right = sortList(temp);
    
    //dummy用于标识新链表头部
    ListNode dummy = new ListNode(-1);
    //cur用来标识当前插入到了哪个节点
    ListNode cur = dummy;
    //排序
    while(left != null && right != null){
        if(left.val <= right.val){
            cur.next = left;
            left = left.next;
        }else{
            cur.next = right;
            right = right.next;
        }
        cur = cur.next;
    }
    //将剩余链表连接上
    cur.next = left == null ? right:left;
    return dummy.next;
    

}