ASSIGNMENT 24

1. Merge Sort For Linked List

To solve this problem efficiently, we use Merge Sort, which follows the Divide and Conquer technique.

Why Merge Sort?
•Linked lists do not support random access
•Splitting and merging are efficient using pointers
•Achieves optimal time complexity O(n log n)

Step-by-Step Explanation

Step 1: Base Condition

If the linked list has:
• 0 nodes or
• 1 node

It is already sorted → return head

Step 2: Find the Middle of the List

We use the slow and fast pointer technique:
•slow moves 1 step
•fast moves 2 steps

When fast reaches the end, slow will be at the middle

Example:
4 → 2 → 1 → 3
•slow stops at 2
•split into:
•Left: 4 → 2
•Right: 1 → 3

Step 3: Split the List

Break the list into two halves:
•Set mid.next = NULL

Now we have two independent lists.

Step 4: Recursively Sort Both Halves

Apply the same process:
• Divide until each list contains only one node

Step 5: Merge Sorted Lists

Now merge the smaller sorted lists:

Example:
•Merge 4 and 2 → 2 → 4
•Merge 1 and 3 → 1 → 3

CODE:

`class Solution:
def sortList(self, head)
if not head or not head.next:
return head

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

    mid = slow.next
    slow.next = None  


    left = self.sortList(head)
    right = self.sortList(mid)


    return self.merge(left, right)

def merge(self, l1, l2):
    dummy = ListNode(0)
    tail = dummy

    while l1 and l2:
        if l1.data < l2.data:
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next

    if l1:
        tail.next = l1
    else:
        tail.next = l2

    return dummy.next`

Complexity Analysis

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

Conclusion

Sorting a linked list efficiently requires a method that works well with its structure. Merge Sort is the best choice because it:

•Does not require random access
•Works efficiently with pointers
•Guarantees optimal time complexity