Sort a Linked List Using Merge Sort

python
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# Function to find middle of linked list
def get_middle(head):
    slow = head
    fast = head.next

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    return slow

# Function to merge two sorted lists
def merge(l1, l2):
    dummy = ListNode()
    tail = dummy

    while l1 and l2:
        if l1.val < l2.val:
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next

    tail.next = l1 if l1 else l2
    return dummy.next

# Merge Sort function
def merge_sort(head):
    if not head or not head.next:
        return head

    mid = get_middle(head)
    right = mid.next
    mid.next = None

    left = merge_sort(head)
    right = merge_sort(right)

    return merge(left, right)

## Input
   4-> 2-> 1-> 3

## output
   1 -> 2 -> 3 -> 4