🧩 Sorting a Linked List Using Merge Sort (Java | GFG Explained)

🚀 Problem Statement

You are given the head of a singly linked list. Your task is to:

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

---

💡 Why Merge Sort for Linked Lists?

Merge Sort is ideal for linked lists because:

• ✔️ No need for random access (unlike arrays)
• ✔️ Splitting is easy using pointers
• ✔️ Merging can be done in-place
• ✔️ Guarantees O(n log n) time complexity

---

🧠 Approach (Divide & Conquer)

Merge Sort works in three main steps:

1️⃣ Divide

Split the list into two halves using the slow and fast pointer technique.

2️⃣ Conquer

Recursively sort both halves.

3️⃣ Combine

Merge the two sorted halves into one sorted list.

---

🔍 Example

Input:
4 -> 2 -> 1 -> 3

Split:
[4 -> 2]   [1 -> 3]

Sort:
[2 -> 4]   [1 -> 3]

Merge:
1 -> 2 -> 3 -> 4

---

⚠️ Important Note for GFG Users

If you’re solving this on GeeksforGeeks, the function name must be:

```java id="x2t7bd"
mergeSort(Node head)

❌ Using `sortList()` will cause a compilation error
✔️ Always match the function name expected by the driver code

---

## 🛠️ Java Implementation (GFG Compatible)



```java id="y38r9k"
class Solution {

    // Function to sort the linked list using Merge Sort
    static Node mergeSort(Node head) {
        // Base case
        if (head == null || head.next == null) {
            return head;
        }

        // Step 1: Find middle
        Node mid = getMiddle(head);
        Node nextOfMid = mid.next;

        mid.next = null; // Split the list

        // Step 2: Sort both halves
        Node left = mergeSort(head);
        Node right = mergeSort(nextOfMid);

        // Step 3: Merge sorted halves
        return merge(left, right);
    }

    // Find middle using slow & fast pointers
    static Node getMiddle(Node head) {
        Node slow = head;
        Node fast = head.next;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }

    // Merge two sorted linked lists
    static Node merge(Node left, Node right) {
        Node dummy = new Node(0);
        Node tail = dummy;

        while (left != null && right != null) {
            if (left.data <= right.data) {
                tail.next = left;
                left = left.next;
            } else {
                tail.next = right;
                right = right.next;
            }
            tail = tail.next;
        }

        // Attach remaining nodes
        tail.next = (left != null) ? left : right;

        return dummy.next;
    }
}

---

⏱️ Complexity Analysis

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

• Time: Each level processes all nodes → O(n), and there are log n levels
• Space: Due to recursion stack

---

📌 Key Concepts to Remember

• Use slow & fast pointers to find the middle
• Always break the list (mid.next = null)
• Use a dummy node for merging
• Merge step is similar to merging two sorted lists

---

❌ Common Mistakes

• Forgetting to split the list → infinite recursion
• Using wrong function name (sortList instead of mergeSort)
• Confusing data with val (GFG uses data)

---

🎯 Final Thoughts

Merge Sort is the best algorithm for sorting linked lists due to its efficiency and compatibility with pointer-based structures.

Once you master this, you’ll be ready for:

• Merge K sorted linked lists
• Linked list partitioning problems
• Advanced recursion challenges

---

🚀 Bonus Tip

Always carefully read platform-specific requirements (like GFG vs LeetCode).
A small mismatch (like method name) can cause compilation errors even if your logic is correct.

---