Leetcode merge sort linked list

Title Description

 

Sample analysis

Subject requirements

 

The time complexity is O(N*logN), At this time complexity, there are only three ： Stack row 、 Quick line up 、 Merge sort , Quickly arrange for the worst case , yes O(N^2), Heap arrangement is not suitable for the sorting of linked lists , So it's only left to merge and sort . 

---

   Method 1 ： From the top down （ recursive ）

Top down approach , That is to split the linked list into two parts in the process of handing it out , Until only the last two nodes are left, it starts to merge back , When I come back , The left and right sequence segments have been ordered respectively , So the merging process is to merge two ordered sequence segments . But it still can't meet the requirements of completing this problem , Here is just a recursive idea , The idea of iteration will be given later .

Code implementation

    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode slow = head;
        ListNode fast = head.next;
        // Speed pointer to split the linked list 
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode midR = slow.next;
        slow.next = null;// Empty the intermediate node is the next recursion  return  Necessary conditions 
        ListNode left = sortList(head);
        ListNode right = sortList(midR);
        // Merge 
        ListNode newHead = new ListNode(0);
        ListNode prev = newHead;;
        while(left != null && right != null) {
            if(left.val <= right.val) {
                prev.next = left;
                left = left.next;
            } else {
                prev.next = right;
                right = right.next;
            }
            prev = prev.next;
        }
        // Come here , Two ordered sequences , One is empty , One is not empty , Connect what is not empty to prev Behind 
        prev.next = (left != null ? left : right);
        return newHead.next;
    }

Drawing analysis

The above figure analyzes the process of distributing and handing out the left half ,2 and 5 After merging, it becomes an ordered sequence segment , and midR On this side is a single ordered sequence segment with only one node , So it confirms the previous explanation .

Complexity analysis

• Time complexity ：O(N*logN) , Is the time complexity of merging and sorting .
• Spatial complexity ：O(logN), The merging of each layer uses auxiliary nodes , So spatial complexity is the height of the tree .

---

  Method 2 ： From the bottom up （ iteration ）

Why can't we achieve constant space complexity from top to bottom , Because every recursion , It is necessary to open up an auxiliary stack space , And first execute the left , The right side has not been implemented , So stack space is not recycled , It will inevitably lead to higher spatial complexity than iteration . The way of iteration is not to operate the whole linked list first like recursion , Further subdivide , It's in order first , Four more four orderly ..., Finally, when subLen = Half the length of the linked list , After executing this cycle , It's all in order .

Code implementation

    public ListNode sortList(ListNode head) {
        if (head == null) {
            return head;
        }
        int len = 0;
        ListNode node = head;
        while (node != null) {
            len++;
            node = node.next;
        }
        ListNode newHead = new ListNode(0, head);
        // Each cycle keeps doubling the left and right sequences 
        for (int subLen = 1; subLen < len; subLen <<= 1) {
            ListNode prev = newHead;
            ListNode cur = newHead.next;
            while (cur != null) {
                ListNode head1 = cur;
                // Move to the tail of the left subsequence 
                for (int i = 1; i < subLen && cur.next != null; i++) {
                    cur = cur.next;
                }
                ListNode head2 = cur.next;
                // Division 
                cur.next = null;
                cur = head2;
                // Move to the tail of the right subsequence 
                for (int i = 1; i < subLen && cur != null && cur.next != null; i++) {
                    cur = cur.next;
                }
                // use next Record the head of the left sequence in the two sequences to be merged next time 
                ListNode next = null;
                if (cur != null && cur.next != null) {
                    next = cur.next;
                    cur.next = null;
                }
                ListNode merged = merge(head1, head2);
                // String the merged sequence after the auxiliary node 
                prev.next = merged;
                while (prev.next != null) {
                    prev = prev.next;
                }
                cur = next;
            }

Drawing analysis

The difference between iteration and recursion can be clearly seen from the figure , It also confirms the above-mentioned two by two order , Four more four orderly , When subLen = 1/2 len When , After executing this cycle, it will be all in order . And iteration really opens up a constant stack space .

Complexity analysis

• Time complexity ： O(N*logN)
• Spatial complexity ： O(1)

This is the end of this article. ！！！