Given a singly-linked list, where each node contains an integer value, sort it in ascending order. The merge sort algorithm should be used to solve this problem.

Examples

null, is sorted to null
1 -> null, is sorted to 1 -> null
1 -> 2 -> 3 -> null, is sorted to 1 -> 2 -> 3 -> null
4 -> 2 -> 6 -> -3 -> 5 -> null, is sorted to -3 -> 2 -> 4 -> 5 -> 6

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution(object):
  def mergeSort(self, head):
    if head is None or head.next is None:
      return head
    head1,head2 = self.split(head)
    p = self.mergeSort(head1)
    q = self.mergeSort(head2)
    return self.merge(p,q)
    """
    input: ListNode head
    return: ListNode
    """
    # write your solution here
  def split(self,head):
    p = head
    q = ListNode(None)
    cur = head
    length = 0
    while cur:
      cur = cur.next
      length += 1
    mid = length/2
    count = 1
    while p is not None:
      if count == mid:
        q.next = p.next
        p.next = None
      p = p.next
      count += 1
    return head,q.next
  
  def merge(self,p,q):
    head = cur = ListNode(0)
    while p and q:
      if p.val > q.val:
        cur.next = q
        q = q.next
      else:
        cur.next = p
        p = p.next
      cur = cur.next
    cur.next = p or q
    return head.next