Sort a Linked List

Problem

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

Examples

Example 1:

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

Example 2:

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

Solution

Method 1 - Insertion Sort

[Insertion Sort on List](insertion-sort-on-list)

Method 2 - Merge Sort

[Merge Sort in a Linked list](merge-sort-in-a-linked-list)