MergeSort Linked List

Moderate
0/80
Average time to solve is 30m
95 upvotes
Asked in companies
InfosysGoogleThought Works

Problem statement

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

Detailed explanation ( Input/output format, Notes, Images )
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 <= N <= 10^5
1 <= DATA <= 10^9

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

Time Limit: 1sec
Sample Input 1 :
1 4 5 2 -1
Sample Output 1 :
1 2 4 5
Sample Input 2 :
10 9 8 7 6 5 4 -1
Sample Output 2 :
4 5 6 7 8 9 10
Hint

If you know the merge sort algorithm for an array, can you extend the same idea to a LinkedList? Think of the changes when you have a LinkedList in place of an array. For example, we cannot get the middle element of the LinkedList directly.

Approaches (1)
Merge Sort Linked List
  1. The idea is to take a recursive approach by calling the sort function on the left half and right half of the list.
  2. 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.
  3. We can now ask the sort function to sort the left and right halves of the list.
  4. 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.
Time Complexity

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)

Space Complexity

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.

Code Solution
(100% EXP penalty)
MergeSort Linked List
Full screen
Console