Given the head of a linked list, return the list after sorting it in ascending order.

Constraints:

• The number of nodes in the list is in the range $[0, 1000]$.

• $-10^3 \leq$ Node.value $\leq 10^3$

The idea of the solution is to sort a linked list using the in-place manipulation of the linked list. This pattern allows us to sort the list without using additional space for storing nodes, using the properties of linked lists, such as pointers, to rearrange nodes directly. The solution employs a divide and conquer approach, similar to merge sort, to sort the elements of the linked list. It starts by finding the middle node of the list using the fast and slow pointers technique. After finding the middle node, it divides the list into two halves. Each half part of the list keeps finding the middle node and dividing it further into parts recursively until no division is possible. Then, it sorts and merges each sublist.

Now, let’s look at the steps of the solution:

1. We begin by checking if the list is empty or contains only one node (i.e., head is NULL or head.next is NULL). If so, we simply return the head as it is already sorted.

2. Next, we find the middle node (mid) of the linked list. This is done using the fast and slow pointers technique, which uses two pointers—a slow pointer that moves one node at a time and a fast pointer that moves two nodes at a time. This ensures that when the fast pointer reaches the end of the list, the slow pointer is at the middle.

   1. Before returning the middle node, we split the linked list into two halves. To do this, we use an additional pointer, prev, which tracks the node immediately before the mid node. Once the middle node is identified, we set prev.next to NULL, allowing each half to be processed independently in subsequent recursive sort operations.

3. Once the sublists contain single nodes, we merge them in sorted order. We create a dummy node (dummy) for merging, and maintaining a pointer (curr) to traverse and build the new sorted list. We compare nodes from both left and right sublists, attaching the node with the smaller value to curr and moving pointers accordingly until one of the sublists has no more nodes. Any remaining nodes in the sublists are directly linked, completing the merge step.

4. Finally, the fully sorted list is returned by returning dummy.next, skipping the initial dummy node used in the merging process.

Let’s look at the following illustration to get a better understanding of the solution: