Skip to content

Instantly share code, notes, and snippets.

@anish000kumar
Last active December 7, 2020 10:11
Show Gist options
  • Save anish000kumar/03b0df0035359dfc5cfacfb0af234197 to your computer and use it in GitHub Desktop.
Save anish000kumar/03b0df0035359dfc5cfacfb0af234197 to your computer and use it in GitHub Desktop.
MergeSort linkedList
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def findMiddle(self, head):
slow, fast = head, head
while fast and fast.next and fast.next.next:
slow, fast = slow.next, fast.next.next
return slow
def merge(self, left, right):
dummy = tail = ListNode()
p1, p2 = left, right
while p1 and p2:
if p1.val < p2.val:
tail.next = p1
p1 = p1.next
else:
tail.next = p2
p2 = p2.next
tail = tail.next
if p1: tail.next = p1
if p2: tail.next = p2
return dummy.next
def sortList(self, head: ListNode) -> ListNode:
if head is None or head.next is None: return head
middle = self.findMiddle(head)
rightNode, middle.next = middle.next, None
left = self.sortList(head)
right = self.sortList(rightNode)
return self.merge(left, right)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment