About usWhy usInstructorsReviewsCostFAQContactBlogRegister for Webinar

Sort Singly Linked List Problem

Problem Statement:

Sort the given singly linked list in ascending order.

You have to do it in-place (using only constant extra space).

Input Format:

There is only one argument named head denoting the head of the given singly linked list.

Output Format:

After sorting, returns the head of the same linked list that is provided in the input.

Constraints:

• 0

• Nodes will contain integer values.

• You have to do it in-place. (You must not create any new node.)

Sample Test Cases:

Sample Test Case 1:

Sample Input 1:

1 -> 7 -> 4 -> 2 -> NULL

Sample Output 1:

1 -> 2 -> 4 -> 7 -> NULL


Sample Test Case 2:

Sample Input 2:

3 -> 2 -> 1 -> 5 -> 4 -> NULL

Sample Output 2:

1 -> 2 -> 3 -> 4 -> 5 -> NULL


Solution

We have provided two solutions and both solutions contain necessary comments to understand the approach used:

To sort linked list in increasing order, we have used insertion sort in brute force solution and merge sort in optimal solution.


1) brute_solution.java

Here we will sort singly linked list using Insertion sort algorithm.

Below is the Insertion sort algorithm for linked list : 


1) Create an empty sorted list (In our code it is sortedListHead).

2) Traverse the given list, do following for every node.

a) Insert current node in sorted way in sortedListHead.

3) returns the sortedListHead.


Example :

List : 3 -> 2 -> 1-> 5 -> 4 -> NULL

Step 1 : 

sortedListHead : NULL

current List : 3 -> 2 -> 1-> 5 -> 4 -> NULL

Step 2 :

sortedListHead : 3 -> NULL

current List : 2 -> 1 -> 5 -> 4 -> NULL

Step 3 :

sortedListHead : 2 -> 3 -> NULL

current List : 1 -> 5 -> 4 -> NULL

Step 4 :

sortedListHead : 1 -> 2 -> 3 -> NULL

current List : 5 -> 4 -> NULL

Step 5 :

sortedListHead : 1 -> 2 -> 3 -> 5 -> NULL

current List : 4 -> NULL

Step 6 :

sortedListHead : 1 -> 2 -> 3 -> 4 -> 5 -> NULL

current List : NULL

Step 7 :

Return sortedListHead.


If we are given sorted linked list in increasing order, then each step will take O(n) time to insert the value in sortedListHead, where n is the length of given linked list. This is the worst case of this solution.

Time Complexity:

O(n^2), here n is length of given singly linked list.

As per the example, number of steps will be n and in worst case each step will take O(n) time to insert the value in sorted list. So, In worst case time complexity will be O(n^2).

Auxiliary Space Used:

O(1).

As we are replacing linked list node to its correct position to sort it in increasing order. Here, we are not using any extra space for this work. So, it is O(1). 

Space Complexity:

O(n).

As input is O(n) and auxiliary space used is O(1).

So, O(n) + O(1) -> O(n).


// -------- START --------

    // Below function is for sort linkedlist using InsertionSort
    
    public static SinglyLinkedListNode sortLinkedList(SinglyLinkedListNode head) {
        
        SinglyLinkedListNode sortedListHead = null; 
        SinglyLinkedListNode current = head; 

        // Traverse the given linked list and insert every node to "sortedListHead"
        
        while (current != null)  
        { 
            // Store next for next iteration 
            SinglyLinkedListNode next = current.next; 
            // insert current in sorted linked list 
            sortedListHead = insertTheNode(sortedListHead, current); 
            // Update current 
            current = next; 
        }
        
        // return 'sortedListHead" node
        
        return sortedListHead;
    }


    // Below function is to insert "nodeTobeInsert" node to "sortedListHead" linkedlist
    
    public static SinglyLinkedListNode insertTheNode(
            SinglyLinkedListNode sortedListHead, SinglyLinkedListNode nodeTobeInsert) {
        
        // Special case for the head end
        if (sortedListHead == null || sortedListHead.data >= nodeTobeInsert.data)  
        { 
            nodeTobeInsert.next = sortedListHead;
            sortedListHead = nodeTobeInsert; 
        } 
        else 
        { 
            SinglyLinkedListNode current = sortedListHead; 

            // Locate the node before the point of insertion
            
            while (current.next != null && current.next.data < nodeTobeInsert.data)  
            { 
                current = current.next; 
            } 
            nodeTobeInsert.next = current.next; 
            current.next = nodeTobeInsert;
        }
        
        return sortedListHead;
    }
    
    // -------- END --------

2) optimal_solution.java

Here we will sort singly linked list using Merge sort.

Below is the Merge sort algorithm for linked list : 

MergeSort(head) :

• If head is NULL or there is only one element in the Linked List then return.

• Else get the middle element of the linked list and divide linked list into two halves (left and right).

• Sort the two halves left and right.

MergeSort(left);

MergeSort(right);


• Merge the sorted left and right halves, and returns the head of merged linked list.

There are two pointers to get middle element of linked list. One is fast pointer and second is slow pointer. At the start, slow pointer points to the first element of linked list and fast pointer points to the second element of linked list. Then fast pointer moves two position ahead and slow pointer moves one position. When fast pointer reach at the end of linked list, slow pointer will points to the middle element of the linked list.


Example:

List : 3 -> 2 -> 1-> 5 -> 4 -> NULL       

Time Complexity: 

O(n * logn).

Auxiliary Space Used:

O(logn).

Due to space used by recursive calls to the function sortLinkedList.

Space Compelxity:

O(n).

As input is O(n) and auxiliary space used is O(logn).

So, O(n) + O(logn) -> O(n).


// -------- START --------

    // Below function is for sort linkedlist using MergeSort
    
    public static SinglyLinkedListNode sortLinkedList(SinglyLinkedListNode head) {
        
        // If head is Null or there is only one element in the linkedlist then return.
        
        if(head == null || head.next == null) {
            return head;
        }
        
        // Get the middle element of linkedlist.
        
        SinglyLinkedListNode middleListNode = getMiddleNode(head);
        SinglyLinkedListNode nextMiddleListNode = middleListNode.next;
        
        /* To devide linkedlist into two halves, put a Null after the middle element.
           So, here "head" pointer points to head of left unsorted linkedlist and 
           "nextMiddleListNode" points to head of right unsorted linkedlist. */
        
        middleListNode.next = null;
        
        // Sorting two halves (left and right).
        // Merge Sort on left linkedlist
        SinglyLinkedListNode leftSortedListNode = sortLinkedList(head);
        
        // Merge Sort on right linkedlist
        SinglyLinkedListNode rightSortedListNode = sortLinkedList(nextMiddleListNode);
        
        // Merging the sorted linkedlist.
        return mergeTwoSortedLists(leftSortedListNode, rightSortedListNode);
        
    }
    
    
    // Below function is to merge sorted linkedlist
    
    public static SinglyLinkedListNode mergeTwoSortedLists(SinglyLinkedListNode a, SinglyLinkedListNode b) {
        
        // If any one linkedlist is null then return other one (Base cases).
        
        if(a == null)
            return b;
        
        if(b == null)
            return a;
        
        // A node to be return, after merging both the sorted linkedlist.
        
        SinglyLinkedListNode headOfMergedList = null, tmpNodeForMergedList = null;
        
        // To keep address of headOfMergedList which is going to be return as head of merged list
        
        if(a.data <= b.data) {
            headOfMergedList = a;
            a = a.next;
        } else {
            headOfMergedList = b;
            b = b.next;
        }
        
        // "tmpNodeForMergedList" points to the end of the linkedlist "headOfMergedList".
        tmpNodeForMergedList = headOfMergedList;
        
        /* We are comparing the top value of linkedlist "a" and linkedlist "b".  
         * Smaller value node will assign to the end of linkedlist "headOfMergedList".
         * We do this until "a" or "b" ends.  
         */
        
        while(a!=null && b!=null) {
            
            if(a.data <= b.data) {
                tmpNodeForMergedList.next = a;
                a = a.next;
                tmpNodeForMergedList = tmpNodeForMergedList.next;
                tmpNodeForMergedList.next = null;
            } else {
                tmpNodeForMergedList.next = b;
                b = b.next;
                tmpNodeForMergedList = tmpNodeForMergedList.next;
                tmpNodeForMergedList.next = null;
            }
            
        }
        
        /* if "b" ends then we assign all remain elements of "a" to end of "headOfMergedList",
         * if "a" ends then we assign all remain elements of "b" to end of "headOfMergedList".
         * and then returns the "headOfMergedList".
         */
        
        if(a!=null) {
            tmpNodeForMergedList.next = a;
        }
        
        if(b!=null) {
            tmpNodeForMergedList.next = b;
        }
        
        return headOfMergedList;
    }
    
    // Below function is to get middle element of the list
    
    public static SinglyLinkedListNode getMiddleNode(SinglyLinkedListNode node) {
        
        if(node == null)
            return node;
        
        SinglyLinkedListNode slowNodePtr = node, fastNodePtr = node.next;
        
        // Move faster pointer by two and slower pointer by one.
        
        while(fastNodePtr != null) {
            fastNodePtr = fastNodePtr.next;
            
            if(fastNodePtr != null) {
                fastNodePtr = fastNodePtr.next;
                slowNodePtr = slowNodePtr.next;
            }
        }
        
        return slowNodePtr;
    }
    
    // -------- END --------