Question

• Assume you have to write a program supporting the operation of merging two sorted lists
into one ”in place” (without creating a copy of the lists). Which kind of data structure
would be more efficient to use? A linked list.

Answer 1

Answer:

Write a Sorted Merge.unction that takes two lists, each of which is sorted in increasing order, and merges the two together into one list which is in increasing order. Sorted Merge  should return the new list. The new list should be made by splicing

together the nodes of the first two lists.

Explanation:

For example if the first linked list a is 5->10->15 and the other linked list b is 2->3->20, then Sorted Merge hould return a pointer to the head node of the merged list 2->3->5->10->15->20.

There are many cases to deal with: either ‘a’ or ‘b’ may be empty, during processing either ‘a’ or ‘b’ may run out first, and finally there’s the problem of starting the result list empty, and building it up while going through ‘a’ and ‘b’.