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, return the head of the same linked list that is provided in the input.

Constraints:

0 <= length of the list <= 10^5
Nodes will contain integer values.
You have to do it in-place (you must not create any new node)

‍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 1: Brute Force Using Insertion Sort (brute_solution.java)

Here we will sort the singly linked list using the insertion sort algorithm. Following is the Insertion sort algorithm for a linked list:

Create an empty sorted list (in our code, it is sortedListHead)
Traverse the given list, do the following for every node:Insert the current node in a sorted way in sortedListHead
Return 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 a sorted linked list in increasing order, each step will take O(n) time to insert the value in sortedListHead, where n is the length of the given linked list. This is the worst case of this solution.

Time Complexity:

O(n^2), where n is the length of the given singly linked list

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

Auxiliary Space Used:

O(1)

As we are placing the linked list node in its correct position to sort it in increasing order, we are not using any extra space.

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 --------

Solution 2: Optimal Solution Using Merge Sort (optimal_solution.java)

Here, we will sort the singly linked list using merge sort. Following is the merge sort algorithm for linked lists:

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 the 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 the merged linked list.

There are two pointers to get the middle element of the linked list — fast pointer and slow pointer. At the start, the slow pointer points to the first element of the linked list, and the fast pointer points to the second element of the linked list.

Then the fast pointer moves two positions ahead, and the slow pointer moves one position. When the fast pointer reaches the end of the linked list, the slow pointer will point 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 the space used by recursive calls to the function sortLinkedList.

Space Complexity:

O(n)

The input is O(n) and auxiliary space used is O(logn). Therefore, 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 --------