Question: Question 3) (20 points) Consider two singly sorted linked lists, L1 and L2, each of which is sorted in ascending (non-decreasing) order. Assume L1 has

Question 3) (20 points) Consider two singly sorted linked lists, L1 and L2, each of which is sorted in ascending (non-decreasing) order. Assume L1 has n entries and L2 has m entries, where n,m>=0. Each entry has two components: a key component of type int and the usual next link component. a) (15 points) Write a C++ Merge function to merge two given lists L1 and L2 in-place. That means your code should result in a singly merged list sorted in ascending order without creating a new list. Your Merge function should return a pointer to the head node of the merged list. Here is an example of how merging would work. Assume the first linked list L1 has 4>35 >95 and the other linked list L2 has 1>7>20>35, your code will produce 1>4>7>20 >35>35>95 without using extra space. b) (5 points) Analyze the time complexity of your code in part (a) in the worst-case. Justify your analysis
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
