LinkedList Merge Sort

Function Name: mergeSortLinkedList

Description

In this challenge, you are tasked with implementing a function that performs a merge sort on a singly linked list. The function should be able to sort the elements of the linked list in ascending order, considering that the nodes hold integer values.

The merge sort algorithm for a linked list is somewhat similar to merge sort for arrays, but rather than using array indices, you will need to manipulate node references and pointers. Your implementation should be efficient and should not just extract values into an array, sort, and recreate the list.

Requirements

• The function mergeSortLinkedList should take a single parameter, which is the head node of the linked list to be sorted.
• Do not use any built-in sorting functions; write the logic for merge sorting manually.
• The function should return the head node of the sorted linked list.
• If the linked list is empty or only contains a single element, the function should return the list as is.
• Define the Node class structure within your solution if not already provided.

Examples

If you have a linked list represented as (3 -> 1 -> 4 -> 2) and you apply your mergeSortLinkedList function, the output should be a linked list (1 -> 2 -> 3 -> 4).

Links