根据网站做软件/互联网营销师怎么报名

题目要求

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

解题思路

首先有一个想法就是，存放所有节点的值然后排序重新建链表。效率的话比较低。
对于本题，我们结合链表的一些常用操作给出一个“归并排序”的思路。什么意思的，就是我们可以把需要排序的链表递归划分，一分为二，二分为四，只到只剩下一个节点（有序的），然后合并两个单节点（合并完也是有序的），然后依次向上合并只到结束。
归并思路：
使用快慢指针确定中点的位置。
分别对左部分和右部分递归。
merge 两部分链表，傀儡节点合并即可。
复杂度分析
快慢指针搜索次数：n / 2 * 1，n / 4 * 2 ，，，，(n / (2^n)) * (2^(n-1))。可以看出是 O(n) 级别。
归并过程的分割次数：1，2，，，logn 次，可以看出分割次数是 O(logn) 级别。
merge 过程不多说了，不管使用递归还是非递归方式实现，时间复杂度都是 O(n) 级别 。
O(nlogn) 的时间：【 分割次数 O(logn) x (快慢指针搜索次数 O(n) + merge 过程 O(n) ) 】= O(nlogn)

主要代码c++

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution(object):def sortList(self, head):""":type head: ListNode:rtype: ListNode"""if head is None or head.next is None:return head# @找链表的中点进行划分fast = headslow = head# 注意这里和判断有没有环（fast and fast.next）的时候是有区别的。while fast.next and fast.next.next:fast = fast.next.nextslow = slow.nextp2 = slow.nextslow.next = None #将l1断开l1 = self.sortList(head) #注意这里是从头开始排序不是从slow！l2 = self.sortList(p2)return self.merge(l1,l2)# @排序过程就是合并链表的过程def merge(self,l1,l2):dummy = tail = ListNode(0)while l1 and l2:if l1.val<l2.val:tail.next = l1l1 = l1.nextelse:tail.next = l2l2 = l2.nexttail = tail.nexttail.next = l1 or l2return dummy.next

原题链接 :https://leetcode-cn.com/problems/sort-list/comments/