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

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

Example:

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

Step 1:

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

Step 2:

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:

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

// Traverse the given linked list and insert every node to "sortedListHead"

while (current != null)
{
// Store next for next iteration
// insert current in sorted linked list
// Update current
current = next;
}

}

// Special case for the head end
{
}
else
{

// 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;
}

}

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

• 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

// If head is Null or there is only one element in the linkedlist then return.

}

// Get the middle element of linkedlist.

/* To devide linkedlist into two halves, put a Null after the middle element.

middleListNode.next = null;

// Sorting two halves (left and right).
// Merge Sort on left linkedlist

// Merge Sort on right linkedlist

return mergeTwoSortedLists(leftSortedListNode, rightSortedListNode);

}

// Below function is to merge sorted linkedlist

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

// To keep address of headOfMergedList which is going to be return as head of merged list

if(a.data <= b.data) {
a = a.next;
} else {
b = b.next;
}

/* 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;
}

}

// Below function is to get middle element of the list

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.

All Posts