Sort a Linked List Using Merge Sort

Introduction

Sorting a linked list efficiently is an important problem in data structures. Merge Sort is the best choice for linked lists because it does not require random access like arrays.

---

Problem Statement

Given the head of a linked list, sort the list in ascending order using Merge Sort.

---

Why Merge Sort for Linked List?

• Works efficiently on linked lists
• Time Complexity: O(n log n)
• Does not require extra space for shifting elements

---

Approach

We use Divide and Conquer:

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

---

Python Code

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