MergeSort Linked List
For a given Singly Linked List of integers, sort the list using the 'Merge Sort' algorithm.

Input format :

The first and the only line of input contains the elements of the linked list separated by a single space.

Remember/Consider :

While specifying the list elements for input, -1 indicates the end of the singly linked list and hence, would never be a list element

Output format :

The only line of output contains the sorted elements of the Singly Linked List in a row, separated by a single space.

Note:

You are not required to print the elements, just sort the elements and return the head to the updated Singly Linked List.

Constraints :

1

Question

MergeSort Linked List

The first and the only line of input contains the elements of the linked list separated by a single space.

While specifying the list elements for input, -1 indicates the end of the singly linked list and hence, would never be a list element

The only line of output contains the sorted elements of the Singly Linked List in a row, separated by a single space.

You are not required to print the elements, just sort the elements and return the head to the updated Singly Linked List.

1 <= N <= 10^5
1 <= DATA <= 10^9

Where 'DATA' denotes the value of node of Linked List.

Time Limit: 1sec

Accepted Answer

Merge Sort Linked List

The idea is to take a recursive approach by calling the sort function on the left half and right half of the list.
In order to do so, get the middle node and split the list into two halves. We can use a two-pointer technique to get the middle node by running a slow and a fast pointer.
1. The idea here is to move both the slow and fast pointer simultaneously until fast reaches the end of the list.
2. Here, for every single step slow takes, fast will make a jump twice of the slow pointer.
3. When the fast pointer reaches the end of the list, the slow pointer will reach the middle of the list.
4. Now you can split into two two lists, by taking slow's next or slow as the head of second list.
5. Make sure to make the tail of first list null.
We can now ask the sort function to sort the left and right halves of the list.
We can assume the lists are now sorted, we now can use the merge two sorted list technique to merge the lists to eventually make the final sorted list and return the new head pointing to the list.

Space Complexity: O(logn)Explanation:

O(log N), where N is the size of the Singly Linked List.

Since we use the recursion stack and at max, we make log (base2) N function calls.

Time Complexity: O(nlogn)Explanation:

O(N * logN), where N is the size of the Singly Linked List.

Recurrence Relation: T(N) = 2T(N/2) + N*K (K is a constant)

Top Samsung Research Software Developer interview questions & answers