Merge Sort for Linked List – Python

🔗 Merge Sort for Linked List – Python (Efficient Sorting)

Hi All,

Today I solved an advanced problem: Sorting a Linked List using Merge Sort.

---

📌 Problem Statement

Given the head of a singly linked list, sort the list using Merge Sort algorithm.

---

🔍 Example

Input:

10 -> 30 -> 20 -> 50 -> 40 -> 60

Output:

10 -> 20 -> 30 -> 40 -> 50 -> 60

---

💡 Why Merge Sort for Linked List?

👉 Unlike arrays:

• Linked lists don’t support random access
• Merge sort works efficiently with pointers

---

💡 Approach

🔹 Divide and Conquer

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

---

🧠 Step-by-Step Logic

Step 1: Find Middle

• Use slow and fast pointers

Step 2: Split List

• Break list into two halves

Step 3: Sort Recursively

Step 4: Merge Two Sorted Lists

---

💻 Python Code

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


# Function to merge two sorted lists
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


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

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

    return slow


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

    # Find middle
    mid = get_middle(head)
    right = mid.next
    mid.next = None  # split

    left = head

    # Sort both halves
    left = merge_sort(left)
    right = merge_sort(right)

    # Merge sorted halves
    return merge(left, right)

---

🔍 Dry Run

For:

10 -> 30 -> 20 -> 50

Steps:

• Split → [10,30] and [20,50]
• Sort → [10,30], [20,50]
• Merge → [10,20,30,50]

---

🖥️ Sample Output

Input: 10 -> 30 -> 20 -> 50 -> 40 -> 60
Output: 10 -> 20 -> 30 -> 40 -> 50 -> 60

---

⚡ Complexity Analysis

• Time Complexity: O(n log n) ✅
• Space Complexity: O(log n) (recursion)

---

🧠 Why this is important?

• Best sorting method for linked list
• Uses divide & conquer
• Frequently asked in interviews

---

✅ Conclusion

This problem helped me understand:

• Merge Sort in linked lists
• Fast & slow pointer technique
• Efficient sorting without extra arrays

🚀 Must-know for coding interviews!

---