ASSIGNMENT 24

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