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