Given a linked list, write a function to rearrange its nodes to be sorted in increasing order. Practice this problem The idea is to use the sortedInsert[] function to sort a linked list. We start with an empty result list. Iterate through the source list and sortedInsert[] each of its nodes into the result list. Be careful to note the .next field in each node before moving it into the result list. Following is the C, Java, and Python program that demonstrates it:
// Helper function to print a given linked list void printList[struct Node* head] printf["%d —> ", ptr->data]; // Helper function to insert a new node at the beginning of the linked list void push[struct Node** head, int data] struct Node* newNode = [struct Node*]malloc[sizeof[struct Node]]; // Function to insert a given node at its correct sorted position into a given // list sorted in increasing order void sortedInsert[struct Node** head, struct Node* newNode] struct Node* current = &dummy; while [current->next != NULL && current->next->data data] { newNode->next = current->next; // Given a list, change it to be in sorted order [using `sortedInsert[]`]. void insertSort[struct Node** head] struct Node* result = NULL; // build the answer here struct Node* current = *head; // iterate over the original list // tricky: note the next pointer before we change it sortedInsert[&result, current]; int keys[] = {6, 3, 4, 8, 2, 9}; int n = sizeof[keys]/sizeof[keys[0]]; // points to the head node of the linked list struct Node* head = NULL; // construct a linked list for [int i = n-1; i >= 0; i--] {
Download Run Code
Output:
2 —> 3 —> 4 —> 6 —> 8 —> 9 —> NULL
Node[int data, Node next] // Helper function to print a given linked list public static void printList[Node head] System.out.print[ptr.data + " —> "]; System.out.println["null"]; // Insert a given node at its correct sorted position into a given // list sorted in increasing order public static Node sortedInsert[Node head, Node newNode] while [current.next != null && current.next.data = 0; i--] { head = new Node[keys[i], head]; |
Download Run Code
Output:
2 —> 3 —> 4 —> 6 —> 8 —> 9 —> null
def __init__[self, data=None, next=None]: # Helper function to print a given linked list print[ptr.data, end=' —> '] # Function to insert a given node at its correct sorted position into a given # list sorted in increasing order def sortedInsert[head, newNode]: while current.next and current.next.data 3 —> 4 —> 6 —> 8 —> 9 —> None The time complexity of the above solution is O[n2], where n is the total number of nodes in the linked list, and doesn’t require any extra space. Please refer below for the merge sort based algorithm to sort a linked list in O[n.log[n]] time.
Thanks for reading. Please use our online compiler to post code in comments using C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages. Like us? Refer us to your friends and help us grow. Happy coding 🙂 Video liên quanChủ Đề |