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 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.dataChủ Đề