Let x =(x1, x2, …, xn) and y = (y1, y2, …., yn) be two linked lists. Write a pro
ID: 3621813 • Letter: L
Question
Let x =(x1, x2, …, xn) and y = (y1, y2, …., yn) be two linked lists. Write a program tomerge the two lists together to obtain the linked list z=(x1, y1, x2, y2,…, xm, ym, xm+1, …, xn) if m= n
and z =( x1, y1, x2, y2, ….xn, yn, yn+1,..,ym) if m>n. following the merge, x and y should not exist as
individual lists because each node initially in x and y is now in z. No additional nodes may be
used. What is the time complexity of your algorithm?
Explanation / Answer
Hope this helps. Let me know if you have any questions. Please rate. :) I included a somewhat trivial main just to show that it works. Feel free to change that as you see fit. Also, I defined the node to hold just an integer so you can see what the final results are. It can hold whatever data you'd like though. The time complexity of this is O(min(n, m)) because once you finish with one of the lists, it just appends the rest of the other list in constant time. #include using namespace std; class node { public: int data; // this can be any sort of data for the list node * next; node(int a) { data = a; next = NULL; }; }; node * merge(node * list1, node * list2) { node * newList = NULL; node * add1; node * add2; node * cur; newList = list1; cur = newList; // base cases - if list1 is null, then just set the newlist to list2 and return if (list1 == NULL) { newList = list2; return newList; } list1 = list1->next; // Since we've already added the first from list1, reverse the order // now start with adding from list2 and then add from list1 while (list1 != NULL && list2 != NULL) { add2 = list2; add1 = list1; list2 = list2->next; list1 = list1->next; cur->next = add2; cur = cur->next; cur->next = add1; cur = cur->next; } // Now clean up - if list1 is null, add the rest of list2 // or if list2 is null, add the rest of list1 if (list1 == NULL) { cur->next = list2; } else if (list2 == NULL) { cur->next = list1; } else { // at the end, so just terminate the list cur->next = NULL; } return newList; } int main() { node * l1 = new node(1); l1->next = new node(5); l1->next->next = new node(70); l1->next->next->next = new node(80); node * l2 = new node(2); l2->next = new node(8); l2->next->next = new node(18); l2->next->next->next = new node(28); l2->next->next->next->next = new node(85); l2->next->next->next->next->next = new node(15); node * l3 = merge(l1, l2); node * cur = l3; while(cur != NULL) { coutRelated Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.