排序链表

题目

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

输入: 4->2->1->3

输出: 1->2->3->4

示例 2:

输入: -1->5->3->4->0

输出: -1->0->3->4->5

思路

代码

public static void main(String[] args) {
        ListNode n1 = new ListNode(4);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(1);
        ListNode n4 = new ListNode(3);

        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        sortList(n1);
    }
    public static ListNode sortList(ListNode head) {
        if(head == null){
            return head;
        }
        return mergeSort(head);
    }

    /**
     * @Author liuhaidong
     * @Description 递归分解序列为两个子序列，并向上并归排序
     *               使用快慢指针法，快指针到终点时慢指针指向中点
     * @param
     * @Date 16:21 2020/1/3 0003
     */
    private static 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);
        return newHead;
    }

    /**
     * @Author liuhaidong
     * @Description 以left节点为起点的左子序列 及 以right为起点的右子序列
     *               并归为一个有序序列并返回头元素；
     * @param
     * @Date 16:26 2020/1/3 0003
     */
    private static ListNode merge(ListNode left, ListNode right) {
        //维护临时序列的头元素
        ListNode head;
        if (left.val<= right.val) {
            head = left;
            left = left.next;
        } else {
            head = right;
            right = right.next;
        }
        //两个子链表均存在剩余元素
        ListNode temp = head;
        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 head;
    }

public class ListNode {
    int val;
    // 保存链表的值
    ListNode next;
    // 下一个结点
    ListNode(int x) {
        val = x; }
}