Sort a Linked List using Merge Sort

In this task, I worked on sorting a singly linked list efficiently. Since linked lists don’t support random access, algorithms like quicksort aren’t ideal. So I used merge sort, which works perfectly with linked lists. What I Did I created a function sortList that: Takes the head of a linked list Sorts it using merge sort Returns the sorted linked list How I Solved It I used the divide and conquer approach: Split the list into two halves Recursively sort both halves Merge the sorted halves Step 1: Find the Middle I used two pointers: slow moves one step at a time fast moves two steps When fast reaches the end, slow will be at the middle. Then I split the list into two halves. Step 2: Recursively Sort I called sortList on both halves: Left half Right half Each half gets sorted independently. Step 3: Merge Two Sorted Lists I used a helper function merge: Compare nodes from both lists Attach the smaller one to the result Continue until one list is exhausted Attach the remaining nodes CODE