Merge Sort for Linked List - CA24

My Thinking and Approach

---

Introduction

In this problem, I was given the head of a linked list and asked to sort it using Merge Sort.

Merge Sort is efficient for linked lists because it does not require random access like arrays.

---

Problem Statement

• Given the head of a linked list
• Sort the linked list using Merge Sort
• Return the sorted list

---

My Initial Thought

At first, I considered:

• Converting the linked list into an array
• Sorting the array
• Rebuilding the linked list

But this approach uses extra space.

---

Key Observation

Merge Sort works well with linked lists because:

• We can split the list into halves easily
• We can merge sorted lists efficiently

---

Optimized Approach

I decided to use Merge Sort with recursion.

Logic:

• Divide the list into two halves
• Recursively sort both halves
• Merge the sorted halves

---

My Approach (Step-by-Step)

1. Base Case:

• If list is empty or has one node → return head

1. Find middle of list:

• Use slow and fast pointer

1. Split the list into two halves

2. Recursively sort both halves

3. Merge the two sorted lists

---

Code (Python)

Below is the implementation clearly separated inside a code block:

```python id="m7x4qp"
class Node:
def init(self, data):
self.data = data
self.next = None

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.sortedMerge(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 sortedMerge(self, left, right):
    if not left:
        return right
    if not right:
        return left

    if left.data <= right.data:
        result = left
        result.next = self.sortedMerge(left.next, right)
    else:
        result = right
        result.next = self.sortedMerge(left, right.next)

    return result

---

## Example Walkthrough

### Input:



```text id="v9q1kz"
10 -> 30 -> 20 -> 40 -> 50 -> 60

Steps:

• Split into halves
• Sort each half recursively
• Merge sorted halves

Output:

```text id="g6x2we"
10 -> 20 -> 30 -> 40 -> 50 -> 60

---

## Complexity Analysis

| Type             | Complexity |
| ---------------- | ---------- |
| Time Complexity  | O(n log n) |
| Space Complexity | O(log n)   |

---

## Key Takeaways

* Merge Sort is efficient for linked lists
* Slow and fast pointers help in splitting
* Merging step is crucial

---

## Conclusion

This problem helped me understand how to apply merge sort on linked lists efficiently without using extra space for arrays.

---