leetcode经典例题第四题，对链表进行排序。

题目描述

Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

Input: 4->2->1->3

Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0

Output: -1->0->3->4->5

解题思路

最近忙着追《都挺好》，差点忘记每天的任务。这一题要求时间复杂度为O(n log n) 并且用常数级别的空间复杂度。对于链表这种数据结构，不像数组那么方便，因此堆排序以及快速排序不是很方便，因此这一题用归并排序比较合适，并且对于本题，空间上不需要用数组来存储，因此是常数级别的。

代码提交

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution {
    //归并排序的归过程
    public ListNode sortList(ListNode head) {
        //1.判定是否为空或者只有一个元素，这也是归并排序中归的停止条件
        if(head == null || head.next == null){
            return head;
        }
        
        //2.将链表截成两段
        ListNode pre = null;
        ListNode slow = head;
        ListNode fast = head;
        
        while(fast != null && fast.next != null){
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        
        //3.此时pre跟slow指的一样，现在将链表从中间断开
        pre.next = null;
        
        //4.继续再对上面分开的链表再分
        ListNode l1 = sortList(head);
        ListNode l2 = sortList(slow);
        
        //5.递归分开之后就应该按照一定的规则合并了
        return merge(l1,l2);
    }
    
    
    //归并排序的并过程
    private ListNode merge(ListNode l1,ListNode l2){
        //新建一个结点用于串联并过程结果
        ListNode tmp = new ListNode(0);
        ListNode p = tmp;
        
        //并的过程，谁小谁就接到p后面
        while(l1!=null && l2!=null){
            if(l1.val < l2.val){
                p.next = l1;
                l1 = l1.next;
            }else{
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }
        
        //如果有一段没有结束，直接接到后面即可
        if(l1 != null){
            p.next = l1;
        }
        
        if(l2 != null){
            p.next = l2;
        }
        
        //返回下一个结点
        return tmp.next;
    }
}