C++ Linked List Insertion program You will write a function that will use the In
ID: 3824777 • Letter: C
Question
C++ Linked List Insertion program
You will write a function that will use the Insertion Sort technique to sort values in a linked list. The basic idea is that you will make a temporary link list. You will start with the first node in your unsorted linked list and insert it into the temporary link list (after the head node with the value 0). Next, you will focus on the second node in your unsorted linked list and insert it into the correct position in the temporary link list. Next, you focus on the third node in your unsorted linked list and insert it into the correct position in the temporary link list. Repeat this process until you have gone through all the nodes in your unsorted linked list. Conceptually, your unsorted linked list is becoming one node smaller in each iteration and your temporary link list gains one node. The key thing to keep in mind is that you are not creating new nodes in the InsertionSort function, you are just rewiring pointers. Therefore, if you start with the head node of the temporary link list and traverse through by following the next pointer, the values will print out in sorted order. That is why at the end, we assign the temporary lists head pointer to the head pointer of the original list.
Outline of code: https://pastebin.com/jb2LaS52
Any help is appreciated. Thank you.
Explanation / Answer
Hi, Please find my implementation of required method.
Please let me know in case of any issue.
/* Link list node */
struct node
{
int data;
struct node* next;
};
// function to sort a singly linked list using insertion sort
node *insertionSort(struct node *head_ref)
{
// Initialize sorted linked list
struct node *sorted = NULL;
// Traverse the given linked list and insert every
// node to sorted
struct node *current = head_ref;
while (current != NULL)
{
// Store next for next iteration
struct node *next = current->next;
// insert current in sorted linked list
sortedInsert(&sorted, current);
// Update current
current = next;
}
// return head node of sorted list
return sorted;
}
/* function to insert a new_node in a list. Note that this
function expects a pointer to head_ref as this can modify the
head of the input linked list (similar to push())*/
void sortedInsert(struct node** head_ref, struct node* new_node)
{
struct node* current;
/* Special case for the head end */
if (*head_ref == NULL || (*head_ref)->data >= new_node->data)
{
new_node->next = *head_ref;
*head_ref = new_node;
}
else
{
/* Locate the node before the point of insertion */
current = *head_ref;
while (current->next!=NULL &&
current->next->data < new_node->data)
{
current = current->next;
}
new_node->next = current->next;
current->next = new_node;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.