This is the 8th day of my participation in Gwen Challenge
Insert sort on linked lists (147)
Topic describes
Starting with the first element, the list can be considered partially sorted (shown in black). At each iteration, an element (shown in red) is removed from the input data and inserted in place into the sorted linked list.
Insert sort algorithm:
- Insertion sort is iterative, moving one element at a time until all the elements can form an ordered output list.
- In each iteration, insert sort removes only one element to be sorted from the input data, finds its proper place in the sequence, and inserts it.
- Repeat until all input data has been inserted.
Example 1:
Input: 4->2->1->3 Output: 1->2->3->4Copy the codeExample 2:
Input: -1->5->3->4->0 Output: -1->0->3->4->5Copy the codeThought analysis
Insertion sorting of linked lists is O(n2){O(n^2)}O(n2) in time and O(1){O(1)}O(1) in space. First, we have a sorted list and an unsorted list, and each time we add one of the unsorted lists to the sorted list, what is the criterion for the newly inserted list node, that is, the list node. Next is greater than the sorted list node.
Then insert the list node at the specified location while continuing to point to the next node.
The code shown
Solution a: time complexity is O (n2) {O (n ^ 2)} O (n2), space complexity is O (1) (1)} {O O (1).
public ListNode insertionSortList(ListNode head) { / / the 2-3-5-7
if (head == null) {
return null;
}
if (head.next == null) {
return head;
}
ListNode newNode = new ListNode(Integer.MIN_VALUE);
ListNode p = head;
while(p ! =null){
ListNode temp = p.next;
ListNode q = newNode; // New list node
while(q.next ! =null && q.next.val <= p.val){ // Loop termination condition 1-2-4 3 q = 2
q = q.next;
}
// Insert the p node
p.next = q.next; //3.next = [2.next = 4]
q.next = p; //2.next = 3
p = temp; //p continues to point to the next node
}
return newNode.next;
}
Copy the codeSorted linked list (148)
Topic describes
Given the head of your list, please sort it in ascending order and return the sorted list.
Advanced:
- You can be in
O(n log n)Sorting linked lists in time complexity and constant space complexity?
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 codeThought analysis
If you are familiar with sorting algorithms, the time complexity is O(nlogn){O(nlogn)}O(nlogn) sorting algorithms include merge sort, heap sort and quicksort, and the worst time complexity of heap sort and quicksort is O(n2){O(n^2)}O(n2), Among them, merge sort is the most suitable sorting algorithm for linked lists, but merge sort is based on didivide and conquer algorithm, and the easiest way to think of is top-down recursive implementation. At this time, the spatial complexity caused by recursive call stack is O(logn){O(logn)}O(logn). If the time complexity of O(1){O(1)}O(1) is achieved, A bottom-up implementation is required.
The code shown
Solution 1: top-down merge sort, time complexity is O(nlogn){O(nlogn)}O(nlogn), space complexity is O(logn){O(logn)}O(logn).
public ListNode sortList(ListNode head) { // merge two ordered lists and sort lists 4,3,2,1
if (head == null) {return null;
}
if (head.next == null) {return head;
}
MidNode = 3; midNode = 3; midNode = 3
ListNode midNode = findMiddleNode(head); / / 4, 3
ListNode secNode = midNode.next; / / 2, 1
midNode.next = null;
ListNode first = sortList(head);
ListNode sec = sortList(secNode);
ListNode newNode = mergetTwoSortedListNode(first,sec);
return newNode;
}
private ListNode mergetTwoSortedListNode(ListNode one,ListNode two){
if (one == null) {return two;
}
if (two == null) {return one;
}
ListNode p = new ListNode();
ListNode newNode = p;
while(one ! =null&& two ! =null) {if (one.val >= two.val){
p.next = two;
two = two.next;
} else {
p.next = one;
one = one.next;
}
p = p.next;
}
if (one == null){
p.next = two;
}
if (two == null){
p.next = one;
}
return newNode.next;
}
private ListNode findMiddleNode(ListNode head){
ListNode quick = head;
ListNode slow = head;
while(quick.next ! =null&& quick.next.next ! =null){
quick = quick.next.next;
slow = slow.next;
}
return slow;
}
Copy the codeThe time complexity is O(nlogn){O(nlogn)}O(nlogn), the space complexity is O(1){O(1)}O(1).
class Solution {
public ListNode sortList(ListNode head) {
if (head == null) {
return head;
}
int length = 0;
ListNode node = head;
while(node ! =null) {
length++;
node = node.next;
}
ListNode dummyHead = new ListNode(0, head);
for (int subLength = 1; subLength < length; subLength <<= 1) {
ListNode prev = dummyHead, curr = dummyHead.next;
while(curr ! =null) {
ListNode head1 = curr;
for (int i = 1; i < subLength && curr.next ! =null; i++) {
curr = curr.next;
}
ListNode head2 = curr.next;
curr.next = null;
curr = head2;
for (int i = 1; i < subLength && curr ! =null&& curr.next ! =null; i++) {
curr = curr.next;
}
ListNode next = null;
if(curr ! =null) {
next = curr.next;
curr.next = null;
}
ListNode merged = merge(head1, head2);
prev.next = merged;
while(prev.next ! =null) { prev = prev.next; } curr = next; }}return dummyHead.next;
}
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;
}
returndummyHead.next; }}Copy the codeconclusion
For the common sorting algorithm, the realization of the array we should master, also should master the insertion sort and merge sort on the linked list.