Sort a Linked List using Merge Sort

Problem Statement

Given the head of a linked list, sort the list in ascending order using merge sort and return the sorted list.

---

Example

Input
4 -> 2 -> 1 -> 3

Output
1 -> 2 -> 3 -> 4

---

Input
-1 -> 5 -> 3 -> 4 -> 0

Output
-1 -> 0 -> 3 -> 4 -> 5

---

Approach Merge Sort on Linked List

Merge sort works by dividing the list into halves, sorting each half, and then merging them.

---

Steps

1 Find the middle of the linked list
2 Split the list into two halves
3 Recursively sort both halves
4 Merge the sorted halves

---

Code

```python id="msll1"
class ListNode:
def init(self, val=0, next=None):
self.val = val
self.next = next

def getMiddle(head):
slow = head
fast = head.next

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

return slow

def merge(l1, l2):
dummy = ListNode(0)
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

if l1:
    tail.next = l1
if l2:
    tail.next = l2

return dummy.next

def sortList(head):
if not head or not head.next:
return head

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

left_sorted = sortList(head)
right_sorted = sortList(right)

return merge(left_sorted, right_sorted)

---

## Explanation

The linked list is divided into two halves using the slow and fast pointer method. Each half is sorted recursively. Finally, both halves are merged into a sorted list.

---

## Expected Output

Input
4 -> 2 -> 1 -> 3

Output
1 -> 2 -> 3 -> 4

---

## Conclusion

Merge sort is very efficient for linked lists because it does not require random access. This problem helps in understanding recursion and linked list manipulation.

Practice this problem to strengthen your understanding of sorting and linked lists.