Advertisement
rishu110067

Untitled

Jan 24th, 2022
999
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. class Solution:
  3.     def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
  4.        
  5.         def helper(h):
  6.             if h is None or h.next is None:
  7.                 return h
  8.            
  9.             r = h
  10.             t = h
  11.            
  12.             while r.next and r.next.next:
  13.                 r=r.next.next
  14.                 t=t.next
  15.                
  16.             h2 = t.next
  17.             t.next = None
  18.            
  19.             list1 = helper(h)
  20.             list2 = helper(h2)
  21.            
  22.             sentinel = ListNode()
  23.             ret = sentinel
  24.            
  25.             while list1 and list2:
  26.                 if list1.val <= list2.val:
  27.                     sentinel.next = list1
  28.                     list1 = list1.next
  29.                 else:
  30.                     sentinel.next = list2
  31.                     list2 = list2.next
  32.                 sentinel = sentinel.next
  33.                    
  34.             while list1:
  35.                 sentinel.next = list1
  36.                 list1 = list1.next
  37.                 sentinel = sentinel.next
  38.             while list2:
  39.                 sentinel.next = list2
  40.                 list2 = list2.next
  41.                 sentinel = sentinel.next
  42.            
  43.             return ret.next
  44.         return helper(head)
  45.        
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement