python - Sort a linked list in O(n log n) time using merge sort -

this algorithm practice of leetcode. , below code:

class listnode:     def __init__(self, x, next=none):         self.val = x         self.next = next  class solution:     # @param head, listnode     # @return listnode     def sortlist(self, head):         if head none or head.next none:             return head         first, second = self.divide_list(head)         self.sortlist(first)         self.sortlist(second)         return self.merge_sort(first, second)      def merge_sort(self, first, second):         if first none:             return second         if second none:             return first         left, right = first, second         if left.val <= right.val:             current, head = left, first             left = left.next         else:             current, head = right, second             right = right.next         while left , right:             if left.val <= right.val:                 current.next = left                 left = left.next             else:                 current.next = right                 right = right.next             current = current.next          if left not none:             current.next = left         if right not none:             current.next = right         return head      def divide_list(self, head):         fast, slow = head.next, head         while fast.next:             slow = slow.next             fast = fast.next             if fast.next:                 fast = fast.next         second_part = slow.next         slow.next = none         return head, second_part 

the idea quite straightforward, basic concept of merge sort. result seems incorrect , running time cost can't pass judgement of leetcode(time limit exceeded, why not o(nlog(n))?). , below test code:

basic test:

c= listnode(3, listnode(1, listnode(2, listnode(4)))) result =solution().sortlist(c) while result:     print result.val     result = result.next # result: 2, 3, 4 missing 1 

anyone have idea optimize code?

the offending lines are

        self.sortlist(first)         self.sortlist(second) 

the problem list head may change after sorting. fix is

        first = self.sortlist(first)         second = self.sortlist(second) 

as general hint, suggest employ sentinel nodes cut down on number of special cases.