“This is the 14th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

Brush algorithm, is never to memorize the problem, but to practice the actual problem into a concrete data structure or algorithm model, and then use the corresponding data structure or algorithm model to solve the problem. In my opinion, with this kind of thinking, I can not only solve the interview problems, but also learn to think in daily work. How to abstract the actual scene into the corresponding algorithm model, so as to improve the quality and performance of the code

Sorting of singly linked lists

Sort linked lists

Topic describes

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

Advanced:

Can you sort a linked list in order n log n time and constant space?

The sample

Example 1

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

Example 2

Input: head = [-1,5,3,4,0]Copy the code

Example 3

Input: head = [] Output: []Copy the code

Tip:

The problem solving

Solution 1: violent solution

Train of thought

When we first see sort, we must think of eight sorting algorithms, but because we want to sort linked lists, it’s hard to use those eight sorting algorithms, because linked lists don’t support random access by index

If you can’t use it, go through the list, pull the values out and put them in an array, and sort the elements of the array. Then join the sorted array elements into a linked list

The idea of brute force is very simple, if you use quicksort, it’s order nlog, because you need a new list, so you need extra space, so the space is order n.

I’m not going to put the code here, but I’m going to look at this sort method

Solution two: merge sort

Train of thought

If you look at merge sort, you might think it’s not O(1) in space, but the elements we’re sorting are in a list, not an array, and we can merge two lists at O(1) in space

Merge sort is essentially a divide-and-conquer idea. The problem is to divide the linked list into two parts. When the linked list is divided to a certain extent, there is only one node left, then it is ordered.

Merge sort is basically looking for the middle position, linked list to find the middle position is very easy, using the fast or slow pointer. The slow pointer moves one node at a time, and the fast pointer moves two nodes at a time. When the fast pointer reaches the end of the linked list, the slow pointer’s position is the midpoint of the linked list

If you don’t know how merge sort works, you can see it here.

code

Func sortList(head *ListNode) *ListNode {return Sort(head, nil)} func Sort(head, nil) tail *ListNode) *ListNode { if head == nil { return head } if head.Next == tail { head.Next = nil return head } slow, fast := head, head for fast ! = tail { slow = slow.Next fast = fast.Next if fast ! = tail { fast = fast.Next } } mid := slow return MergeList(Sort(head, mid), Sort(mid, tail)) } func MergeList(head1, Dummy := dummy, head2 *ListNode) *ListNode {dummy := &ListNode{} tmpNode, tmpNode2 := dummy, head1, head2 for tmpNode1 ! = nil && tmpNode2 ! = nil { if tmpNode1.Val <= tmpNode2.Val { tmpNode.Next = tmpNode1 tmpNode1 = tmpNode1.Next } else { tmpNode.Next = tmpNode2 tmpNode2 = tmpNode2.Next } tmpNode = tmpNode.Next } if tmpNode1 ! = nil { tmpNode.Next = tmpNode1 } if tmpNode2 ! = nil { tmpNode.Next = tmpNode2 } return dummy.Next }Copy the code