Advertisement
Iam_Sandeep

Merge Sort for linked list

Apr 2nd, 2022
1,188
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.12 KB | None | 0 0
  1.  
  2. class Solution:
  3.     def mergeSort(self, head):
  4.         def mid(x):
  5.             s=f=x
  6.             while f.next and f.next.next:
  7.                 s,f=s.next,f.next.next
  8.             return s
  9.         def merge(h):
  10.             if not h or not h.next:return h
  11.             m=mid(h)
  12.             L,R=h,m.next
  13.             m.next=None
  14.             l=merge(L)
  15.             r=merge(R)
  16.             dum=res=Node('-1')
  17.             while l and r:
  18.                 if l.data<r.data:
  19.                     res.next=Node(l.data)
  20.                     l=l.next
  21.                 elif l.data>r.data:
  22.                     res.next=Node(r.data)
  23.                     r=r.next
  24.                 else:
  25.                     res.next=Node(r.data)
  26.                     res=res.next
  27.                     res.next=Node(l.data)
  28.                     l,r,=l.next,r.next
  29.                 res=res.next
  30.             while l:
  31.                 res.next=Node(l.data)
  32.                 l,res=l.next,res.next
  33.                
  34.             while r:
  35.                 res.next=Node(r.data)
  36.                 r,res=r.next,res.next
  37.             return dum.next
  38.         return merge(head)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement