算法-链表排序-蒲公英云

算法-链表排序

1. 链表排序

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

链接：leetcode 原题

2. 解法

归并排序：

首先将链表从中部切分为两个部分，不断递归这个过程
递归回溯的时候将两个链表归并为有序链表

public ListNode sortList(ListNode head) {
        return null == head ? null : mergeSort(head);
    }
    public ListNode mergeSort(ListNode head) {
        if (Objects.isNull(head.next)) {
            return head;
        }
        ListNode slow = head;
        ListNode fast = head;
        ListNode mid = null;
        while (null != fast && null != fast.next) {
            mid = slow;
            fast = fast.next.next;
            slow = slow.next;
        }
        // mid.next == slow, 从链表中间位置将其后的节点断开
        mid.next = null;
        ListNode node1 = mergeSort(head);
        ListNode node2 = mergeSort(slow);
        return mergeTwoLists(node1, node2);
    }
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (null == l1) return l2;
        if (null == l2) return l1;
        ListNode dummyHead = new ListNode(0);
        ListNode p = dummyHead;
        while (null != l1 && null != l2) {
            if (l1.val > l2.val) {
                p.next = l2;
                l2 = l2.next;
            } else {
                p.next = l1;
                l1 = l1.next;
            }
            p = p.next;
        }
        p.next = null == l1 ? l2 : l1;
        return dummyHead.next;
    }