# 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, 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.

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

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

#### 2) optimal_solution.java

Here we will sort singly linked list using Merge sort.

Below is the Merge sort algorithm for linked list :

• 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

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

All Posts