Make writing a habit together! This is the 15th day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.

preface

The order list of question 148 is as follows:

Given the head of your list, please sort it in ascending order and return the sorted list.

Example 1:

Input: head = [4,2,1,3] output: [1,2,3,4]Copy the code

A, thinking

Insert a list into an ascending order. Insert a list into an ascending order.

You can pass this if you just insert sort using yesterday’s code. Another very simple idea is as follows:

  1. Walk through the linked list, collecting all the elements
  2. Arrange the collected elements in ascending order
  3. Iterate through the list again, taking the sorted element values and modifying each element

I could have done it like this, but it would have taken O(n) space to store each node, and that wouldn’t have been good enough.

Merge sort

So how do you do that? Since you want order N logN in time and constant space, it’s easy to think of merge sort. The core idea of merge sort is: split first, then merge

Here, head = [4,2,1,3] is used as an example. The splitting principle is to split the list in the middle until there are only two elements in the sub-list (one element does not need to be reordered, so it can be split into two elements).

  1. The process of splitting

The linked list will eventually be split into the following two sub-linked lists

  1. Process of merging

The process of merging is to sort the elements of the sublists and then merge the sorted sublists, that is, merge the two ascending lists.

To sum up, the steps for using merge sort are roughly as follows:

  1. userecursiveTo break up linked lists
  2. Arrange the sublists in ascending order
  3. Multiple sub-lists are combined in pairs with ascending lists

Second, the implementation

The implementation code

The implementation code is consistent with the idea

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

public ListNode dfs(ListNode head, ListNode tail){
    if (head == null)
        return null;
    if (head.next == tail){
        head.next = null;
        return head;
    }
    // Split in the middle
    ListNode fast = head;
    ListNode slow = head;
    while(fast ! = tail){ slow = slow.next; fast = fast.next;if(fast ! = tail) fast = fast.next; } ListNode listNode1 = dfs(head, slow); ListNode listNode2 = dfs(slow, tail );return mergeTwoLists(listNode1, listNode2);

}

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode ret = new ListNode();
    ListNode temp = ret;
    / / iteration
    while(l1 ! =null&& l2 ! =null) {
        if (l1.val < l2.val) {
            temp.next = l1;
            l1 = l1.next;
        } else {
            temp.next =l2;
            l2 = l2.next;
        }
        temp = temp.next;
    }
    // Categorize untraversed lists into results
    if (l1 == null) {
        temp.next = l2;
    }
    if (l2 == null)
        temp.next = l1;
    return ret.next;
}
Copy the code

The test code

public static void main(String[] args) {
    ListNode list = new ListNode(4.new ListNode(2.new ListNode(1.new ListNode(3))));
    ListNode ret = new Number148().sortList(list);
    System.out.println("test");
}
Copy the code

The results of

Third, summary

Thank you to see the end, very honored to help you ~♥

If you think my writing is good, you might as well give me a thumbs-up! If you have any questions, please see the comments section