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

太过爱你忘了你带给我的痛 2022-05-26 02:50 77阅读 0赞

> 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(nlogn)，空间复杂度为常量

> 思路：

对链表排序，只能使用**归并排序**。归并排序是将两个或两个以上的有序链表合并成一个新的链表。常见的是二路归并排序算法，思想是将数组或链表中前后相邻的两个有序序列归并为一个有序序列，时间复杂度为o(nlogn)，需要等数量的辅助空间。

/**
     * Definition for singly-linked list.
     * class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) {
     *         val = x;
     *         next = null;
     *     }
     * }
     */
    public class Solution {
        public ListNode sortList(ListNode head) {
            if(head == null || head.next == null)
                return head;
            ListNode slow = head;
            ListNode fast = head;
            while(fast != null && fast.next != null && fast.next.next != null){
                slow = slow.next;
                fast = fast.next.next;
            }
            fast = slow;
            slow = slow.next;
            fast.next = null;
            fast = sortList(head);
            slow = sortList(slow);
            return mergeSort(fast,slow);
        }
        private ListNode mergeSort(ListNode s1,ListNode s2){
            if(s1 == null)
                return s2;
            if(s2 == null)
                return s1;
            ListNode newHead = null;
            if(s1.val <= s2.val){
                newHead = s1;
                s1 = s1.next;
            }else{
                newHead = s2;
                s2 = s2.next;
            }
            ListNode p = newHead;
            while(s1 != null && s2 != null){
                if(s1.val <= s2.val){
                    p.next = s1;
                    s1 = s1.next;
                }else{
                    p.next = s2;
                    s2 = s2.next;
                }
                p = p.next;
            }
            if(s1 != null){
                p.next = s1;
            }
            if(s2 != null){
                p.next = s2;
            }
            return newHead;
        }
    }