Sort a Linked List

You are tasked with sorting a singly linked list in ascending order. Sorting a linked list is a fundamental data structure operation that is crucial for many algorithms and data management tasks. Efficiently sorting a linked list often requires different approaches compared to sorting arrays due to its sequential access nature.

Problem Description

Your goal is to implement a function that takes the head of a singly linked list as input and returns the head of the sorted list. The sorting should be done in ascending order of the node values.

Key Requirements:

• The function must sort the linked list in place if possible, or return a new head of the sorted list.
• The sorting should be stable if the node values are not unique (though for this challenge, assume unique values for simplicity in explanation, but consider how duplicates might be handled).
• The original structure of the linked list should be modified or a new sorted list constructed.

Expected Behavior:

Given a linked list, rearrange its nodes such that their values are in non-decreasing order.

Edge Cases to Consider:

• An empty list.
• A list with only one node.
• A list that is already sorted.
• A list sorted in reverse order.

Examples

Example 1:

Input: Head of a linked list representing [4, 2, 1, 3]
Output: Head of a linked list representing [1, 2, 3, 4]
Explanation: The nodes have been rearranged to form a sorted list.

Example 2:

Input: Head of a linked list representing [-1, 5, 3, 4, 0]
Output: Head of a linked list representing [-1, 0, 3, 4, 5]
Explanation: The list is sorted in ascending order.

Example 3:

Input: Head of a linked list representing [1]
Output: Head of a linked list representing [1]
Explanation: A single-node list is already sorted.

Constraints

• The number of nodes in the list will be between 0 and 50,000.
• Node values will be integers between -100,000 and 100,000.
• The algorithm should aim for an optimal time complexity.

Notes

Consider different sorting algorithms and how they can be adapted to a linked list. Algorithms like Merge Sort are often well-suited for linked lists due to their divide-and-conquer nature and ability to work efficiently with sequential data. In-place sorting might be challenging for some algorithms, so returning a new head is acceptable. Pseudocode for a node structure might look like:

Node:
  value: Integer
  next: Pointer to Node or null