148. Sort linked lists
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?
Example 1:
Input: head = [4,2,1,3] output: [1,2,3,4]
Example 2:
Input: head = [-1,5,3,4,0]
Example 3:
Input: head = [] Output: []
Tip: The number of nodes in the list is in the range [0, 5 * 104] -105 <= node. val <= 105
I still don’t have a good understanding of the recursion, so let’s think about the recursion
Thinking: At present, only sketchy thoughts can be recorded
Recursion works best with trees and linked lists with Pointers, so if you take one node out of the middle you get another tree or another whole linked list, so if you have two trees on the left and the right of a tree, you split the problem, if you split the middle of a linked list into two linked lists, you split the problem again.
Recursion and looping or dynamic programming are reversed, and if you can do it with low-level loops, you can usually do it with upper-level recursion.