# Costed 2536ms using python, how to optimize?

• My code used mergesort and fast-slow pointers to divide the list. I cannot find any time-consuming bottlenecks in my code. But in the distribution I saw a lot of 500ms or even 250ms python solutions. Got confused... Can anyone help me to improve? (I also tried to covert the linked list into an array, sort by built-in method sort() then convert back. This way used 248ms but I believe those python solutions under 2500ms were not all doing it this way)

``````# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
# @return {ListNode}
def mergeTwoLists(self, l1, l2):
while l1 or l2:
if l1 and l2 and l1.val < l2.val or not l2:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next

while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
slow.next = None
l1 = self.sortList(l1)
l2 = self.sortList(l2)
return self.mergeTwoLists(l1, l2)``````

• My python merge sort code, which costs ~1800ms. It's quite strange, why Python code in this case is so costly?

``````def sortList(self, head):

while fast and fast.next:
fast = fast.next.next
slow = slow.next
l1 = self.mergeSort(slow.next)
slow.next = None
return self.merge(l1, l2)

def merge(self, l1, l2):
dummy = curr = ListNode(0)
while l1 and l2:
if l1.val < l2.val:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next
curr = curr.next
curr.next = l1 or l2
return dummy.next``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.