Won't you insist on 71 days? List sorting

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

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 22 Step , Each time the slow pointer moves 11 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 .

Sort the two sub linked lists separately .

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 11, That is, when the linked list is empty or the linked list only contains 11 When a node , There is no need to split and sort the linked list .

class Solution {
    public ListNode sortList(ListNode head) {
        return sortList(head, null);
    }

    public ListNode sortList(ListNode head, ListNode tail) {
        if (head == null) {
            return head;
        }
        if (head.next == tail) {
            head.next = null;
            return head;
        }
        ListNode slow = head, fast = head;
        while (fast != tail) {
            slow = slow.next;
            fast = fast.next;
            if (fast != tail) {
                fast = fast.next;
            }
        }
        ListNode mid = slow;
        ListNode list1 = sortList(head, mid);
        ListNode list2 = sortList(mid, tail);
        ListNode sorted = merge(list1, list2);
        return sorted;
    }

    public ListNode merge(ListNode head1, ListNode head2) {
        ListNode dummyHead = new ListNode(0);
        ListNode temp = dummyHead, temp1 = head1, temp2 = head2;
        while (temp1 != null && temp2 != null) {
            if (temp1.val <= temp2.val) {
                temp.next = temp1;
                temp1 = temp1.next;
            } else {
                temp.next = temp2;
                temp2 = temp2.next;
            }
            temp = temp.next;
        }
        if (temp1 != null) {
            temp.next = temp1;
        } else if (temp2 != null) {
            temp.next = temp2;
        }
        return dummyHead.next;
    }
}

 author ：LeetCode-Solution
 link ：https://leetcode.cn/problems/7WHec2/solution/lian-biao-pai-xu-by-leetcode-solution-0rjx/
 source ： Power button （LeetCode）
 The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .