InterviewSolution
Saved Bookmarks
InterviewSolution
| 1. |
A given linked list is sorted based on absolute values. Write a function to sort the list based on actual values in O(n) time. |
|
Answer» All the NEGATIVE elements can be found in the reverse ORDER. Therefore, as we traverse the list, whenever we find an ELEMENT that is out of order, it is MOVED to the front of the linked list. Auxiliary Space: O(1) Implementation: void sortList(Node** head){ // Initialize the previous and the current nodes Node* previous = (*head); Node* current; // list traversal for(current = (*head)->next; current != NULL; current = current->next) { // continue if the current element // is at its right place if (current->value >= previous->value) { previous = current; } // If current is smaller than previous, then // it must be moved to head else { // Detach current from the linked list previous->next = current->next; // MOVE the current node to the beginning current->next = (*head); (*head) = current; // Update current current = previous; } }} |
|