Merge Sort Linked List
You are given a Singly Linked List of integers. Sort the Linked List using merge sort.

Merge Sort is a Divide and Conquer algorithm. It divides the input into two halves, calls itself for the two halves, and then merges the two sorted halves. The merge() function is used for merging two halves. The merge(arr, L, M, R) is a key process that assumes that arr[L..M] and arr[M + 1...R] are sorted and merges the two sorted subarrays into one.

Input Format:

The first line of input contains a single integer T, representing the number of test cases or queries to be run. Then the T test cases follow. The first line of each test case contains the elements of the singly linked list separated by a single space and terminated by -1. Hence, -1 would never be a list element.

Output Format:

For each test case, print the sorted linked list. The elements of the sorted list should be single-space separated, terminated by -1. The output of each test case is printed in a separate line.

Note:

You are not required to print the output, it has already been taken care of. Just implement the function.

Constraints :

1

Question

Merge Sort Linked List

You are given a Singly Linked List of integers. Sort the Linked List using merge sort.

Merge Sort is a Divide and Conquer algorithm. It divides the input into two halves, calls itself for the two halves, and then merges the two sorted halves. The merge() function is used for merging two halves. The merge(arr, L, M, R) is a key process that assumes that arr[L..M] and arr[M + 1...R] are sorted and merges the two sorted subarrays into one.

Input Format:

The first line of input contains a single integer T, representing the number of test cases or queries to be run. 
Then the T test cases follow.

The first line of each test case contains the elements of the singly linked list separated by a single space and terminated by -1. Hence, -1 would never be a list element.

Output Format:

For each test case, print the sorted linked list. The elements of the sorted list should be single-space separated, terminated by -1.

The output of each test case is printed in a separate line.

Note:

You are not required to print the output, it has already been taken care of. Just implement the function.

Constraints :

1 <= T <= 10
1 <= N <= 10^4
-10^9 <= data <= 10^9 and data != -1

Where data is the value associated with the node.

Time Limit: 1 sec

Accepted Answer

Merge Sort

We will use the ‘Merge Sort’ algorithm to sort the given linked list. Merge Sort is a Divide and Conquer algorithm. In this algorithm, we will divide the list into two parts, recursively sort the two parts and finally merge them such that the resultant list will be sorted.

Algorithm:

If the list contains only one node, return the head of the list.
Else, divide the list into two sublists. For this, we will take pointers ‘MID’ and ‘TAIL’ which will initially point to the head node. We will change ‘MID’ and ‘TAIL’ as follows until ‘TAIL’ becomes NULL:
‘MID’ = ‘MID’ -> next
‘TAIL’ = ‘TAIL’ -> next -> next.

The above operation will ensure that ‘MID’ will point to the middle node of the list. ‘MID’ will be the head of the second sublist, so we will change the ‘NEXT’ value of the node which is before mid to NULL.

Call the same algorithm for the two sublists.
Merge the two sublists and return the head of the merged list. For this, we will take a pointer to a node, ‘MERGE_LIST’, which will be initially pointing to NULL. If the head of the first sublist has a value less than the head of the second sublist then we will point the ‘MERGE_LIST’ to the head of the first sublist and change the head to its next value. Else, we will point the ‘MERGE_LIST’ to the head of the second sub list.
In the end, if any of the sublists becomes empty and the other sublist is non-empty, then we will add all nodes of the non-empty sublist in the 'MERGE_LIST’.

Space Complexity: O(logn)Explanation:

O(log2(N)), where ‘N’ is the number of nodes in the linked list.

Since the algorithm is recursive and there are log2(N) levels, it requires O(log2(N)) stack space.

Time Complexity: OtherExplanation:

O(N * log2(N)), Where ‘N’ is the number of nodes in the linked list.

The algorithm used (Merge Sort) is divide and conquer. So, for each traversal, we divide the list in 2 parts, thus there are log2(N) levels and the final complexity is O(N * log2(N)).

Java (SE 1.8)

/*

    Time Complexity: O(N*log(N))

    Space complexity: O(log(N))

    

    Where N is the number of nodes in the linked list.

*/



public class Solution {

    public static Node sortLL(Node head) {

        head = sortLLHelpler(head);

        return head;

    }



    static Node merge(Node firstHead, Node secondHead) {

        Node mergeList = null;

        Node cur = null;



        // Placing the nodes in sorted order and simultaneously merging the two lists.

        while (firstHead != null && secondHead != null) {

            if (firstHead.data < secondHead.data) {



                if (mergeList == null) {

                    mergeList = firstHead;

                    cur = firstHead;

                } 

				

				else {

                    cur.next = firstHead;

                    cur = cur.next;

                }



                firstHead = firstHead.next;

            } 

			else {

                if (mergeList == null) {

                    mergeList = secondHead;

                    cur = secondHead;

                } else {

                    cur.next = secondHead;

                    cur = cur.next;

                }

                secondHead = secondHead.next;

            }

        }



	    // If any of the list is left, append it at the end of currently merged list.

        if (firstHead != null) {

            cur.next = firstHead;

        }



        if (secondHead != null) {

            cur.next = secondHead;

        }

        return mergeList;

    }



    static Node sortLLHelpler(Node head) {

        if (head == null || head.next == null) {

            return head;

        }



        // Dividing list into two sublists.

        Node mid = head;

        Node tail = head;

        Node prev = new Node(-1);



        while (tail != null && tail.next != null) {

            prev = mid;

            mid = mid.next;

            tail = tail.next.next;

        }



        prev.next = null;

        Node firstHead = head;

        Node secondHead = mid;



        // Calling the recursive function on sub-lists.

        firstHead = sortLLHelpler(firstHead);

        secondHead = sortLLHelpler(secondHead);



        head = merge(firstHead, secondHead);

        return head;

    }



}

C++ (g++ 5.4)

/*

    Time Complexity: O(N*log(N))

    Space complexity: O(log(N))

    

    Where N is the number of nodes in the linked list.

*/



Node *merge(Node *firstHead, Node *secondHead){

  Node *mergeList = NULL, *cur = NULL;

	

	// Placing the nodes in sorted order and simultaneously merging the two lists.

    while (firstHead != NULL && secondHead != NULL){

        if (firstHead->data < secondHead->data){



            if (mergeList == NULL){

                mergeList = firstHead;

                cur = firstHead;

            }



            else{

                cur->next = firstHead;

                cur = cur->next;

            }

            firstHead = firstHead->next;

        }

        else

        {

            if (mergeList == NULL){

                mergeList = secondHead;

                cur = secondHead;

            }

            else{

                cur->next = secondHead;

                cur = cur->next;

            }

            secondHead = secondHead->next;

        }

    }



	// If any of the list is left, append it at the end of currently merged list.

    if (firstHead != NULL){

        cur->next = firstHead;

    }

    if (secondHead != NULL){

        cur->next = secondHead;

    }



    return mergeList;

}



Node *sortLLHelper(Node *head){

    if (head == NULL || head->next == NULL){

        return head;

    }



    // Dividing list into two sublists.

    Node *mid = head, *tail = head, *prev;

    while (tail != NULL && tail->next != NULL){

        prev = mid;

        mid = mid->next;

        tail = tail->next->next;

    }

    prev->next = NULL;



    Node *firstHead = head;

    Node *secondHead = mid;



    // Calling the recursive function on sub-lists.

    firstHead = sortLLHelper(firstHead);

    secondHead = sortLLHelper(secondHead);



    head = merge(firstHead, secondHead);



    return head;

}



Node *sortLL(Node *head){

    head = sortLLHelper(head);

    return head;

}

Python (3.5)

'''

    Time Complexity: O(N*log(N))

    Space complexity: O(log(N))

    

    Where N is the number of nodes in the linked list.

'''



def merge(firstHead, secondHead):

    mergeList, cur = None, None



    # Placing the nodes in sorted order and simultaneously merging the two lists.

    while (firstHead != None and secondHead != None):

        if (firstHead.data < secondHead.data):



            if (mergeList == None):

                mergeList = firstHead

                cur = firstHead



            else:

                cur.next = firstHead

                cur = cur.next



            firstHead = firstHead.next

        else:



            if (mergeList == None):

                mergeList = secondHead

                cur = secondHead



            else:

                cur.next = secondHead

                cur = cur.next

            secondHead = secondHead.next



    # If any of the list is left, append it at the end of currently merged list.

    if (firstHead != None):

        cur.next = firstHead



    if (secondHead != None):

        cur.next = secondHead



    return mergeList





def sortLLHelper(head):

    if (head == None or head.next == None):

        return head



    # Dividing list into two sublists.

    mid, tail = head, head

    prev = None



    while (tail != None and tail.next != None):

        prev = mid

        mid = mid.next

        tail = tail.next.next



    prev.next = None



    firstHead = head

    secondHead = mid



    # Calling the recursive function on sublists.

    firstHead = sortLLHelper(firstHead)

    secondHead = sortLLHelper(secondHead)



    head = merge(firstHead, secondHead)



    return head





def sortLL(head):

    head = sortLLHelper(head)

    return head

You are given a Singly Linked List of integers. Sort the Linked List using merge sort.

Input Format:

Output Format:

Note:

Constraints :

Top Sourcefuse Technologies Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern