【Leetcode】148.排序链表

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

方法(归并排序思路)

  1. 首先用快慢指针法将链表从中间断开
  2. 对左边链表排序
  3. 对右边链表排序
  4. 合并左右两个链表，返回链表头

代码

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
public ListNode sortList(ListNode head) {
    if(head == null)
        return null;
    //递归中止条件：链表只有一个节点
    if(head.next == null)
        return head;
    //快慢指针，快指针走到尾，慢指针走到中点
    ListNode fast = head, slow = head;
    while(fast.next != null && fast.next.next != null){
        fast = fast.next.next;
        slow = slow.next;
    }
    //从中点将链表断成两部分
    ListNode tail = slow;
    slow = slow.next;
    tail.next = null;
    ListNode L = sortList(head);
    ListNode R = sortList(slow);
    return merge(L, R);
}

public ListNode merge(ListNode left, ListNode right){
    ListNode dummy = new ListNode(0);
    ListNode cur = dummy;
    while(left != null && right != null){
        if(left.val <= right.val){
            cur.next = left;
            cur = cur.next;
            left = left.next;
        }
        else{
            cur.next = right;
            cur = cur.next;
            right = right.next;
        }
    }
    if(left != null)
        cur.next = left;
    if(right != null)
        cur.next = right;
    return dummy.next;
}