Write a C++ function given two sorted linked lists a: [2 3 4 9 10 30] b: [5 8 8
ID: 3747254 • Letter: W
Question
Write a C++ function given two sorted linked lists
a: [2 3 4 9 10 30]
b: [5 8 8 11 20 40]
That merges these two lists in sorted order. Do not alllocate or deallocate any memory, just relink the nodes.
After call it should look like:
a: [2 3 4 5 8 8 9 10 11 20 30 40]
b: []
The linked list has a data value a next pointer to the next node. It also has a front pointer that points to the front of the list and a back pointer that points to the back of the list.
Time Complexity: O(length of first list + length of second list)
Explanation / Answer
Let me know if you have any doubt.
Function to Sort two sorted array:
struct Node* SortedMerge(struct Node* a, struct Node* b)
{
struct Node* result = NULL;
/* point to the last result pointer */
struct Node** lastPtrRef = &result;
while(1)
{
if (a == NULL)
{
*lastPtrRef = b;
break;
}
else if (b==NULL)
{
*lastPtrRef = a;
break;
}
if(a->data <= b->data)
{
MoveNode(lastPtrRef, &a);
}
else
{
MoveNode(lastPtrRef, &b);
}
/* tricky: advance to point to the next ".next" field */
lastPtrRef = &((*lastPtrRef)->next);
}
return(result);
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.