Merge Sort for Linked List

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

def mergeSort(head):
    # Base case: if list is empty or has one node
    if not head or not head.next:
        return head
    
    # Find the middle of the list using slow and fast pointers
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    second_half = slow.next
    slow.next = None
    
    # Recursively sort the two halves
    left = mergeSort(head)
    right = mergeSort(second_half)
    
    # Merge the sorted halves
    return merge(left, right)

def merge(left, right):
    dummy = ListNode(0)
    current = dummy
    
    # Merge two sorted lists
    while left and right:
        if left.val <= right.val:
            current.next = left
            left = left.next
        else:
            current.next = right
            right = right.next
        current = current.next
    
    # Append remaining nodes
    current.next = left if left else right
    return dummy.next

# Helper function to create linked list from array
def createLinkedList(arr):
    if not arr:
        return None
    head = ListNode(arr[0])
    current = head
    for val in arr[1:]:
        current.next = ListNode(val)
        current = current.next
    return head

# Helper function to convert linked list to array for printing
def linkedListToArray(head):
    result = []
    current = head
    while current:
        result.append(current.val)
        current = current.next
    return result

# Example usage
arr = [4, 2, 1, 3]
head = createLinkedList(arr)
sorted_head = mergeSort(head)
print(linkedListToArray(sorted_head))  # Output: [1, 2, 3, 4]