class Solution:
    def mergeSort(self, head):
        def mid(x):
            s=f=x
            while f.next and f.next.next:
                s,f=s.next,f.next.next
            return s
        def merge(h):
            if not h or not h.next:return h
            m=mid(h)
            L,R=h,m.next
            m.next=None
            l=merge(L)
            r=merge(R)
            dum=res=Node('-1')
            while l and r:
                if l.data<r.data:
                    res.next=Node(l.data)
                    l=l.next
                elif l.data>r.data:
                    res.next=Node(r.data)
                    r=r.next
                else:
                    res.next=Node(r.data)
                    res=res.next
                    res.next=Node(l.data)
                    l,r,=l.next,r.next
                res=res.next
            while l:
                res.next=Node(l.data)
                l,res=l.next,res.next
                
            while r:
                res.next=Node(r.data)
                r,res=r.next,res.next
            return dum.next
        return merge(head)