Loading problem...
You are given the head of a singly linked list containing integer values. Your task is to rearrange the nodes of the linked list so that all values appear in ascending order (from smallest to largest).
The sorting must be performed by rearranging the actual nodes in the linked list, not merely by swapping or copying values between nodes. Return the head of the newly sorted linked list.
This problem tests your understanding of linked list manipulation and efficient sorting algorithms. Consider how traditional sorting techniques need to be adapted for linked list data structures where random access is not available.
head = [4,2,1,3][1,2,3,4]The linked list 4 → 2 → 1 → 3 is rearranged to 1 → 2 → 3 → 4 by sorting the nodes in ascending order. Each node is repositioned based on its value.
head = [-1,5,3,4,0][-1,0,3,4,5]The linked list -1 → 5 → 3 → 4 → 0 is sorted to produce -1 → 0 → 3 → 4 → 5. Negative values are placed at the beginning, followed by non-negative values in ascending order.
head = [][]An empty linked list remains empty after sorting. This is an edge case where no nodes exist to be sorted.
Constraints