Merge Sort for Linked List

Hi everyone!
Today I worked on sorting a linked list using Merge Sort. Unlike arrays, we can’t directly apply quick access techniques, so merge sort works best here.

Problem
Given a linked list, sort it using merge sort.
Example:
Input: 10 -> 50 -> 30 -> 20

Output: 10 -> 20 -> 30 -> 50

My Approach
Sorting a linked list is tricky because:

• No random access (like arrays)
• Need efficient splitting and merging So I used: > Merge Sort (Divide & Conquer)

Logic

1. Find middle of list using slow & fast pointers
2. Split the list into two halves
3. Recursively sort both halves
4. Merge the sorted halves

Code (Python)
class Solution:

def mergeSort(self, head):
    if not head or not head.next:
        return head

    mid = self.getMiddle(head)
    next_to_mid = mid.next
    mid.next = None

    left = self.mergeSort(head)
    right = self.mergeSort(next_to_mid)

    return self.merge(left, right)


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

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

    return slow


def merge(self, left, right):
    dummy = Node(0)
    tail = dummy

    while left and right:
        if left.data <= right.data:
            tail.next = left
            left = left.next
        else:
            tail.next = right
            right = right.next
        tail = tail.next

    if left:
        tail.next = left
    else:
        tail.next = right

    return dummy.next

Time & Space Complexity

• Time: O(n log n)
• Space: O(log n) (recursion stack)

Key Insight
Merge sort is preferred for linked lists because:

• No need for extra shifting like arrays
• Easy to split using pointers

What I Learned

• Divide & conquer is very powerful
• Fast & slow pointer technique is useful
• Merge sort is ideal for linked lists

Thanks for reading!
Feel free to share any improvements or doubts.