给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

示例 1：

 

输入：head = [4,2,1,3]输出：[1,2,3,4]

示例 2：

 

输入：head = [-1,5,3,4,0]输出：[-1,0,3,4,5]

示例 3：

输入：head = []输出：[]

思路：

  这个题乍一看是将链表进行排序。以前好像从来没有接触过如何排序链表，可以用像排序普通数组那样的排序方法来排序吗？是可以的。

  这里我们可以使用归并排序的思路来解决。归并排序依然是用递归方法，总体思路就是：把要排序的数组分成两部分，对两部分再进行归并排序，排好后将这两部分有序数组合并到一起。只要定义好归并排序的base case（比如个数为1时直接返回），这个问题就解决了。

  如果有归并排序的基础，上面写的就很好理解了。现在问题转变为：在链表上进行归并排序，怎么类似地把链表分成两部分？用快慢指针。我们虽然不知道链表的长度，但我们定义一个一次走一步的慢指针和一个一次走两步的快指针，当快指针到达终点时，满指针所处的位置就是中间切分点！

  那base case如何定义呢？我们对分出来的每一部分继续进行归并排序，那么当只剩一个节点或者传入为空的时候，我们就不需要再分成两部分了吧，直接返回当前即可，这就是base case。

  那么如何把排序好的两部分进行合并呢？这不就是合并两个有序链表问题吗？我这里采用非递归的方法，开辟第三个结果链表，逐一把两个链表中较小的值添加到结果链表。因为这个也不是这道题的重点，具体细节就不再描述了，代码里体现即可。

代码：

class Solution(object):

    def sortList(self, head):

        def merge_sort(head):#merge_sort功能就是对传入链表归并排序，返回排序好结果

            #定义base case

            if not head or not head.next:#如果为空，或只有一个节点

                return head#直接返回自己

            slow,fast=head,head.next#fast初始化为head.next,如果初始化head则死循环

                #fast初始化为head.next也可以保证slow无论怎样都正好到达前半段的结尾

            while fast and fast.next:#快指针的判断到头与否，和环形链表题方法一致

                slow=slow.next#慢指针走一步

                fast=fast.next.next#快指针走两步

            #现在慢指针来到了第一部分的末尾

            head2 = slow.next#慢指针的下一个节点当成新的头结点head2

            slow.next=None#慢指针指向空，让第一部分链表独立出来

            return merge(merge_sort(head),merge_sort(head2))#两部分分别排序，再merge

        def merge(root1,root2):#merge方法，合并两个有序链表问题而已

            p = ListNode()#定义第三个链表

            q = p#q暂存头结点

            while root1  and root2:#两个指针分别游走于两个链表，取小放进第三个链表

                if root1.val<=root2.val:#root1小

                    p.next=root1

                    p=p.next

                    root1= root1.next

                else:#root2小

                    p.next=root2

                    p=p.next

                    root2 = root2.next

            p.next=root1 if root1 else root2#把其中没有遍历完链表剩下部分全部加进结果

            return q.next

        return merge_sort(head)

小结：

  从递归函数的整体来看，merge_sort先利用快慢指针将链表分成两部分，分别进行归并排序后，将结果合并，返回排序好后的头结点，逻辑是自洽的，不需跳进下一层的递归。一切都自然而然地交给自动递归和base case来处理。

   实现起来要注意的细节有对fast指针的初始化，要初始化为head.next，这样可以保证当fast到达终点（最终节点或者最终节点的下一位）时，slow的位置在前半段的结尾。这种小结论是因结果出错（实践出真知）所总结出来的，自己动手画一下图就可以理解了。