链表题，递归方法简单，但调用隐式栈，空间复杂度O(logN),方法二是用迭代代替递归的那部分，即找中点

排序链表
递归法，空间复杂度O(logn)
class Solution:def sortList(self, head: ListNode) -> ListNode:if not head or not head.next: #head为空或只有headreturn headslow, fast = head , head.nextwhile fast and fast.next:fast , slow = fast.next.next , slow.nextmid , slow.next = slow.next , None #这4行固定双指针找中点的模板#分割找中点，边排序边合并left ,right = self.sortList(head) , self.sortList(mid)h = res = ListNode(0) #定义merge环节中的头部节点，作为最终返回值while left and right:if left.val < right.val:h.next ,left = left ,left.next#从小到大排序，将小值加入head.next，并递归下一个值else:h.next , right = right ,right.nexth = h.next#h作为辅助节点不断向后遍历h.next = left if left else right #将剩下的还存在的值直接加入head.nextreturn res.next #h和res都作为辅助节点，h是不断遍历的，res作为辅助节点直接返回就是result，链表题常用操作

class Solution:def sortList(self, head: ListNode) -> ListNode:h, length, intv = head, 0, 1while h: h, length = h.next, length + 1res = ListNode(0)res.next = head# merge the list in different intv.while intv < length:pre, h = res, res.nextwhile h:# get the two merge head `h1`, `h2`h1, i = h, intvwhile i and h: h, i = h.next, i - 1if i: break # no need to merge because the `h2` is None.h2, i = h, intvwhile i and h: h, i = h.next, i - 1c1, c2 = intv, intv - i # the `c2`: length of `h2` can be small than the `intv`.# merge the `h1` and `h2`.while c1 and c2:if h1.val < h2.val: pre.next, h1, c1 = h1, h1.next, c1 - 1else: pre.next, h2, c2 = h2, h2.next, c2 - 1pre = pre.nextpre.next = h1 if c1 else h2while c1 > 0 or c2 > 0: pre, c1, c2 = pre.next, c1 - 1, c2 - 1pre.next = h intv *= 2return res.next

方法二参考链接