Register for our webinar

How to Nail your next Technical Interview

1 hour
Loading...
1
Enter details
2
Select webinar slot
*Invalid Name
*Invalid Name
By sharing your contact details, you agree to our privacy policy.
Step 1
Step 2
Congratulations!
You have registered for our webinar
check-mark
Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
*All webinar slots are in the Asia/Kolkata timezone
Step 1
Step 2
check-mark
Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.
close-icon
Iks white logo

You may be missing out on a 66.5% salary hike*

Nick Camilleri

Head of Career Skills Development & Coaching
*Based on past data of successful IK students
Iks white logo
Help us know you better!

How many years of coding experience do you have?

Thank you! Your submission has been received!
Oops! Something went wrong while submitting the form.
Iks white logo

FREE course on 'Sorting Algorithms' by Omkar Deshpande (Stanford PhD, Head of Curriculum, IK)

Thank you! Please check your inbox for the course details.
Oops! Something went wrong while submitting the form.
closeAbout usWhy usInstructorsReviewsCostFAQContactBlogRegister for Webinar
Our June 2021 cohorts are filling up quickly. Join our free webinar to Uplevel your career
close

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: 

  1. Create an empty sorted list (in our code, it is sortedListHead)
  2. Traverse the given list, do the following for every node:
    Insert the current node in a sorted way in sortedListHead
  3. 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 --------

<Code snippet 1>

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



Try yourself in the Editor

Note: Input and Output will already be taken care of.

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: 

  1. Create an empty sorted list (in our code, it is sortedListHead)
  2. Traverse the given list, do the following for every node:
    Insert the current node in a sorted way in sortedListHead
  3. 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 --------

<Code snippet 1>

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



Worried About Failing Tech Interviews?

Attend our free webinar to amp up your career and get the salary you deserve.

Ryan-image
Hosted By
Ryan Valles
Founder, Interview Kickstart
blue tick
Accelerate your Interview prep with Tier-1 tech instructors
blue tick
360° courses that have helped 14,000+ tech professionals
blue tick
100% money-back guarantee*
Register for Webinar

Recommended Posts

All Posts