Leetcode148.排序链表——排序问题详解

引入

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

题目要求时间空间复杂度分别为O(nlogn)和O(1)，根据时间复杂度我们自然想到二分法，从而联想到归并排序。

归并排序解法

归并排序一般需要两步：

1. sort阶段
2. merge阶段

废话不多说sort如下代码所示：

public void sort(int[] arr, int L, int R) {
    if(L == R) {
        return;
    }
    int mid = L + ((R - L) >> 1);
    sort(arr, L, mid);
    sort(arr, mid + 1, R);
    merge(arr, L, mid, R);
}

不过本题难点在于：如何获取到mid？ 链表的mid节点不能通过运算得来，我们想到以前的一个方法：快慢指针。

    public ListNode mergeSort(ListNode head) {
        //回归条件
        if (head.next == null) {
            return head;
        }
        //快指针,考虑到链表为2时的情况，fast比slow早一格
        ListNode fast = head.next;
        //慢指针
        ListNode slow = head;
        //快慢指针开跑
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //找到右子链表头元素，复用fast引用
        fast = slow.next;
        //将中点后续置空，切割为两个子链表
        slow.next=null;
        //递归分解左子链表,得到新链表起点
        head=mergeSort(head);
        //递归分解右子链表,得到新链表起点
        fast=mergeSort(fast);
        //并归两个子链表
        ListNode newHead = merge(head, fast);
//        ListNode.print(newHead);
        return newHead;
    }

这里还将listnode进行断链的处理，是真真正正的二分。以便于标记结束的节点是空。然后通过merge将两个链合成一个链即可。

接下来是merge阶段：
只需要用一个dummy来承接接下来的

    public ListNode merge(ListNode left, ListNode right) {
    	ListNode dummy=new ListNode(-1);
        ListNode temp = dummy;
        while (left != null && right != null) {
            //将较小的元素加入临时序列
            if (left.val <= right.val) {
                temp.next=left;
                left = left.next;
                temp = temp.next;
            } else {
                temp.next=right;
                right = right.next;
                temp = temp.next;
            }
        }
        //左子序列用完将右子序列余下元素加入临时序列
        if (left == null) {
            temp.next=right;
        }
        //右子序列用完将左子序列余下元素加入临时序列
        if (right == null) {
            temp.next=left;
        }
        return dummy.next;
    }

其他

上述排序算法，有机会再补充，这里由于快速排序在面试中用到的比较多，贴下代码：

public class test {
    public static void main(String[] args) {
        int[] arr=new int[]{113,223,52,12,543,322,110,6534,77,32,141};
        quickSort(arr,0,arr.length-1);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
    }
    public static void quickSort(int[] arr,int left,int right){
        if(left<right){
            int mid=getIndex(arr,left,right);
            quickSort(arr,left,mid-1);
            quickSort(arr,mid+1,right);
        }
    }
    public static int getIndex(int[] arr,int left,int right){
        int temp=arr[left];
        while(left<right){
            while(left<right&&arr[right]>temp) right--;
            arr[left]=arr[right];
            while(left<right&&arr[left]<temp) left++;
            arr[right]=arr[left];
        }
        arr[left]=temp;
        return left;
    }
}

其他排序算法代码参考：十大排序算法。