Problem

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

Examples

Example 1:

1
2

Input: head = [4,2,1,3]
Output: [1,2,3,4]

Example 2:

1
2

Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]

Solution

Method 1 - Insertion Sort

Insertion Sort on List

Method 2 - Merge Sort

Merge Sort in a Linked list