# Sort List

Sort a linked list inO(nlogn) time using constant space complexity.

## Merge Sort

这道题要找linkedlist中点，那当然就要用最经典的faster和slower方法，faster速度是slower的两倍，当faster到链尾时，slower就是中点，slower的next是下一半的开始点

```
# 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
        """
        def merge(list1, list2):
            if not list1:
                return list2
            if not list2:
                return list1
            head = None
            if list1.val > list2.val:
                head = list2
                list2 = list2.next
            else:
                head = list1
                list1 = list1.next
            tmp = head
            while list1 and list2:
                if list1.val > list2.val:
                    tmp.next = list2
                    tmp = list2
                    list2 = list2.next
                else:
                    tmp.next = list1
                    tmp=list1
                    list1=list1.next
            tmp.next = list1 or list2
            return head
        if not head or not head.next:
            return head
        slow = head
        fast = head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        mid = slow.next
        slow.next = None
        list1 = self.sortList(head)
        list2 = self.sortList(mid)
        sorted = merge(list1, list2)
        return sorted
```

关于快慢节点找中点：

<https://www.jiuzhang.com/qa/4283/>

如果fast = head，在节点是奇数个的时候，应当和fast = head.next的结果是一致的。但是如果节点是偶数的时候，比如说`10个的时候`, 如果设置fast = head.next ,那么 slow 会得到第5个节点（中间靠前），如果设置fast = head，那么slow 会得到第6的节点（中间考后）

**就是当偶数个时候，我们得到的是中间靠前面那个节点，还是中间靠后面那个节点，具体需要看题目的要求**，比如LintCode的题目上是要求中间靠前那个节点（也就是10个节点里第5个节点），所以fast = head.next.如果需要中间考后的节点，fast=head即可。

对于这道题，里面也运用到了找Middle的方法，这里fast是可以等于head的，也就是fast = head，和 fast = head.next 都对。因为对于排序，你找到10个节点中的第5个还是第6个，对答案没有影响。