【LEETCODE】148-Sort List[Python]

Sort a linked list in O(n logn)time using constant space coplexity.
件名:
チェーンの並べ替え、O(n) ロゴ n)time，constant space coplexity
考え方:
時間と空間の複雑さに対する題意の要求によって、ここで並べ替えて使います。
参考:
並べ替え:
http://blog.csdn.net/littlethunder/article/details/9472301
http://bookshadow.com/weblog/2014/11/21/leetcode-sort-list/
Python

# 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
        
        mid=self.getmiddle(head)
        lHead=head
        rHead=mid.next
        mid.next=None
        
        return self.merge(self.sortList(lHead),self.sortList(rHead))
    
    def getmiddle(self,head):
        
        if head is None:
            return head
            
        fast=slow=head
        
        while fast.next and fast.next.next:
            slow=slow.next
            fast=fast.next.next
        
        return slow
        
    
    def merge(self,lHead,rHead):
        dumNode=ListNode(0)
        dumHead=dumNode
        
        i=lHead
        j=rHead
        
        while i and j:
            if i.val<j.val:
                dumNode.next=i
                i=i.next
            else:
                dumNode.next=j
                j=j.next
            dumNode=dumNode.next
        
        if i:
            dumNode.next=i
        if j:
            dumNode.next=j
        
        return dumHead.next