preface
Hello everyone, I am a little boy picking up field snails, today we will look at a very classic leetcode real problem: sort linked list
- Public number: a boy picking up snails
The title
Given the head of your list, please sort it in ascending order and return the sorted list. The time is order n log n.
Example 1:
Input: head = [4,2,1,3] output: [1,2,3,4]Copy the codeExample 2:
Input: head = [-1,5,3,4,0]Copy the codeAnalysis of the
Sorting algorithm selection
The time requirement is order n log n, so it’s easy to think of quicksort, and merge sort.
Let’s review the quick sort, its basic idea is: by a trip to sort to sort data split into separate two parts, one part of all the data are smaller than the other part of all data, and then of the two parts data respectively according to the method of quick sort, the entire sorting process can be recursive, to achieve the whole data into an orderly sequence.
In other words, quicksort needs to find the base value, some of the data is smaller than this base value, some of the data is larger than this base value. Because this is a linked list, even after finding the reference value, it is not easy to operate. Therefore, merge sort algorithm can be considered.
Core steps of merge sort algorithm
The core steps of merge sort are as follows:
- The sequence of length N to be sorted is divided into two subsequences of length N /2;
- For these two subsequences, merge sort is used respectively.
- Combine two sorted subsequences into a final ordered sorted sequence.
For a linked list, unlike a regular data sequence, it finds an intermediate node and then cuts it off. So with merge sort, the operation to unlist a linked list looks something like this:
- Walk through the list to find the middle node.
- When the intermediate node is found, cut it off
- Then merge sort, respectively, to arrange the left and right sublists
- Merge sublists
How do I find intermediate nodes using merge sort?
We can use double Pointers, one fast pointer, one slow pointer.
The fast pointer takes two steps at a time, while the slow pointer takes only one. When the fast pointer goes to the end of the list, the slow pointer goes to the middle node.
So, to find the code for the middle node of the list, we could write:
ListNode slow = head; ListNode fast = head; while(fast.next! =null && fast.next.next ! =null){ fast = fast.next.next; slow = slow.next; }Copy the codeWhen the intermediate node is found, cut it off
Once you find the intermediate node, how do you cut it off?
We can cut it by assigning the next pointer to the slow node to the new variable mid, and then cutting the next pointer to the slow node to null. As shown in figure:
So the code could be written like this:
// Next pointer to mid ListNode mid = slow. slow.next = null;Copy the codeThen merge sort, respectively, to arrange the left and right sublists
If we were to sort head and mid by sortList, we would have to sort them the same way.
ListNode leftList = sortList(head); ListNode rightList = sortList(mid);Copy the codeMerge sublists
We want to merge both ordered list, turn it into a new order list, actually can use among a linked list, and then respectively through left and right child list, compare the two list value of the current node, which is small, put it into the middle list, and small value of node in the linked list, working lixia a node.
Graphical merge process
So let me draw a little diagram just to make sense of it.
Suppose the left, right, and middle lists to sort are as follows:
First, take the value 1 of the left list and compare it with the value 3 of the right list. Since 1 is less than 3, put the node with the value 1 into the middle list, and the left list moves a node, and the middle list moves a node to the right, as shown in the figure:
Next, take the value 5 of the left list and compare it with the value 3 of the right list. Since 5 is greater than 3, put the node with the value 3 into the middle list, and move a node from the right list to the middle list, as shown in the figure:
Next, take the value 5 of the left list and compare it with the value 4 of the right list. Since 5>4, put the node with the value 4 in the middle list, and move a node from the right list to the middle list, as shown in the figure:
Immediately, take the value 5 of the left list and compare it with the value 6 of the right list. Since 5 is less than 6, put the node with the value 5 in the middle list, and the left list moves a node, and the middle list moves a node, as shown in the figure:
Finally, because the left list has been traversed and the right list has not been traversed, we can put the right list in the middle list (officially speaking, the next pointer in the middle list points to the right list), as shown in the following figure:
At this point, the list has been merged, but it’s not what we want, because we have an additional initial node 0 and a pointer to 5. What to do? We want 1-> 3-> 4 ->5 ->6.
We can initialize head by assigning it to temp, then let temp move it, and return next of head.
Merge code implementation
Let’s implement the code according to the diagram, as follows:
Public ListNode merge(ListNode left, ListNode right) {// Merge head = new ListNode(0); // Merge head = new ListNode(0); // assign head to the intermediate variable temp. ListNode temp = head; while (left ! = null && right ! If (left.val <= right.val) {//temp points to a node with a small value (the left list has a small value) temp.next = left; // Left = left. Next; } else {//temp points to nodes with small values (right list with small values) temp.next = right; // Move the list right one node right = right.next; } // Move the middle list pointer down a node temp = temp.next; } // If the left sublist is not empty, then the next pointer to temp points to it if (left! = null) { temp.next = left; // If the right sublist is not empty, then the next pointer to temp points to it} else if (right! = null) { temp.next = right; } // return head. Next; }Copy the codeIf you don’t understand the code, go back to the diagram.
Full code implementation
By traversing the list to find the middle node, cutting the list from the middle node, sorting the left and right sub-lists by merge sort, and merging sub-lists, we can combine the complete code as follows:
Class Solution {public ListNode sortList(ListNode head) {// If the list is empty, or there is only one node, return the list. Don't have to sort the if (head = = null | | head. The next = = null) return the head; ListNode slow = head; ListNode slow = head; ListNode fast = head; while(fast.next! =null && fast.next.next ! =null){ fast = fast.next.next; slow = slow.next; } // Next pointer to mid ListNode mid = slow. Next; // Cut the list slow. Next = null; ListNode left = sortList(head); // Sort left sublist ListNode right = sortList(mid); Return merge(left,right); } public ListNode merge(ListNode left, ListNode right) { ListNode head = new ListNode(0); ListNode temp = head; while (left ! = null && right ! = null) { if (left.val <= right.val) { temp.next = left; left = left.next; } else { temp.next = right; right = right.next; } temp = temp.next; } if (left ! = null) { temp.next = left; } else if (right ! = null) { temp.next = right; } return head.next; }}Copy the codeGo to Leetcode and submit it.
