daily pastebin goal
33%
SHARE
TWEET

Untitled

a guest Mar 20th, 2019 71 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution:
  2.     def sortList(self, head: ListNode) -> ListNode:
  3.         def getSize(hd):
  4.             size = 0
  5.             node = hd
  6.             while node:
  7.                 size += 1
  8.                 node = node.next
  9.             return size
  10.         def split(hd):
  11.             size = getSize(hd)
  12.             node = hd
  13.             for _ in range(size//2-1):
  14.                 node = node.next
  15.             tmp = node.next
  16.             node.next = None
  17.             return hd, tmp
  18.         def merge(hd1, hd2):
  19.             node1, node2 = hd1, hd2
  20.             sent = ListNode(666)
  21.             tail = sent
  22.             def ins(x):
  23.                 nonlocal tail
  24.                 tail.next = x
  25.                 tail = x
  26.             while node1 and node2:
  27.                 if node1.val < node2.val:
  28.                     ins(node1)
  29.                     node1 = node1.next
  30.                 else:
  31.                     ins(node2)
  32.                     node2 = node2.next
  33.             if node1:
  34.                 ins(node1)
  35.             if node2:
  36.                 ins(node2)
  37.             return sent.next
  38.         def mergeSort(hd):
  39.             if not hd or not hd.next:
  40.                 return hd
  41.             hd1, hd2 = split(hd)
  42.             hd1 = mergeSort(hd1)
  43.             hd2 = mergeSort(hd2)
  44.             return merge(hd1, hd2)
  45.         return mergeSort(head)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top