[leetcode] linked list sorting (gradually increasing the space-time complexity)

An interview question , List sorting .

List sorting

1. Title Description

leetcode Topic link ：148. Sort list

Advanced ： You can O(n log n) Under time complexity and constant space complexity , Sort the linked list ？

2. Thought analysis

The time complexity of this problem is better than O(n2) Sort algorithm . The advanced problem of the subject is required to meet the requirements O(nlog⁡n) Time complexity and O(1) Spatial complexity of , The time complexity is O(nlog⁡n) The sorting algorithm includes merge sorting 、 Heap sort and quick sort （ The worst time complexity of quick sort is O(n2), One of the most suitable sorting algorithms for linked lists is merge sorting .

Method 1 ： Heap sort

The simplest and direct way ：

1. The definition type is ListNode The smallest pile
2. Building the heap ： Linked list all node Into the heap
3. Eject the top of the stack one by one node, That is, from small to large
4. Time complexity O(nlogn), Spatial complexity O(n)
5. This method is almost the same as the heap sorting of arrays , It's the easiest thing to do , It's not easy to make mistakes.

Method 2 ： Top down merge sort

Optimize space complexity .

The process of merging and sorting the linked list from top to bottom is as follows .

1. Find the midpoint of the list , With the midpoint as the boundary , Split the linked list into two sub linked lists . To find the midpoint of the linked list, you can use the fast and slow pointer , Every time the fast pointer moves 2 Step , Each time the slow pointer moves 1 Step , When the fast pointer reaches the end of the linked list , The linked list node pointed to by the slow pointer is the midpoint of the linked list .
2. Sort the two sub linked lists separately .
3. Merge the two sorted sub linked lists , Get the complete sorted linked list .

The above process can be implemented recursively . The termination condition of recursion is that the number of nodes in the linked list is less than or equal to 1, That is, when the linked list is empty or the linked list only contains 1 When a node , There is no need to split and sort the linked list .

Complexity analysis

• Time complexity ：O(nlog⁡n), among n It's the length of the list .
• Spatial complexity ：O(log⁡n), among n It's the length of the list . The space complexity mainly depends on the stack space of recursive calls .

Method 3 ： Bottom up merge sort

Further optimize the space complexity .

Spatial complexity O(1). Start from a single node and merge into a multi segment ordered linked list ; Merge the multi segment ordered linked list in pairs , Until it is merged into a complete linked list .

3. Code implementation

Method 1 ： Heap sort

class Solution {
    
    public ListNode sortList(ListNode head) {
    
        //  Heap sort 
        PriorityQueue<ListNode> queue = new PriorityQueue<>((a, b) -> a.val - b.val);  //  Small cap pile 
        while (head != null) {
      //  Add all to the small top pile 
            queue.offer(head);
            head = head.next;
        }
        //  Out of pile , Assign a value to the new linked list 
        ListNode dumpy = new ListNode();
        ListNode cur = dumpy;
        while (queue.size() > 0) {
    
            cur.next = queue.poll();
            cur = cur.next;
        }
        cur.next = null;
        return dumpy.next;

    }
}

Method 2 ： Top down merge sort

class Solution {
    
    public ListNode sortList(ListNode head) {
    
        //  If the list is empty , Or just one node , Go straight back to , No sorting 
        if (head == null || head.next == null)  return head;

        //  Fast and slow double pointer movement , Find intermediate nodes 
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
    
            fast = fast.next.next;
            slow = slow.next;
        }
        //  Find the middle node ,slow Node next Pointer to mid
        ListNode mid = slow.next;
        //  Cut off the linked list 
        slow.next = null;
        //  Sort the left sub linked list 
        ListNode left = sortList(head);
        //  Sort right sub linked list 
        ListNode right = sortList(mid);
        //  Merge list 
        return merge(left, right);
    }
    public ListNode merge(ListNode left, ListNode right) {
    
        ListNode head = new ListNode(0);
        ListNode tmp = head;
        while (left != null && right != null) {
    
            if (left.val <= right.val) {
    
                tmp.next = left;
                left = left.next;
            } else {
    
                tmp.next = right;
                right = right.next;
            }
            tmp = tmp.next;
        }
        if (left != null) {
    
            tmp.next = left;
        } else if (right != null) {
    
            tmp.next = right;
        }
        return head.next;
    }
}