Guest User

Untitled

a guest
Dec 8th, 2019
93
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution:
  2.     def getLength(self, head):
  3.         cnt = 1
  4.         while(head.next != None):
  5.             head = head.next
  6.             cnt = cnt + 1
  7.         return cnt
  8.     def sort(self, preArray, l, r):        
  9.         if(l + 1 >= r):
  10.             return preArray
  11.         mid = (l + r) // 2
  12.         head = preArray
  13.         preArray = self.sort(preArray, l, mid)
  14.         array = preArray.next
  15.         array2 = array
  16.         preArray2 = preArray
  17.         for i in range(l, mid):
  18.             preArray2 = preArray2.next
  19.             array2 = array2.next
  20.         preArray2 = self.sort(preArray2, mid, r)
  21.         array = preArray.next
  22.         array2 = preArray2.next
  23.         lpoint = l
  24.         midpoint = mid
  25.         while(lpoint < midpoint and midpoint < r):
  26.  
  27.             if(array.val < array2.val):
  28.                 array = array.next
  29.                 preArray = preArray.next
  30.                 lpoint = lpoint + 1
  31.             else:
  32.                 array2Next = array2.next
  33.                 preArray.next = array2
  34.                 array2.next = array
  35.                 preArray2.next = array2Next
  36.                 preArray = preArray.next
  37.                 array2 = array2Next
  38.                 midpoint = midpoint + 1
  39.                 lpoint = lpoint + 1
  40.         return head
  41.        
  42.     def sortList(self, head: ListNode) -> ListNode:
  43.         if(head == None):
  44.             return head
  45.         preHead = ListNode(-1)
  46.         preHead.next = head
  47.         length = self.getLength(head)
  48.         preHead = self.sort(preHead, 0, length)
  49.         return preHead.next
RAW Paste Data