6-Ans- This original version of this question had Array instead of Linked List. This question was asked in one of the Google interviews, I guess ! To make it more difficult I have replaced the Arrays with the Linked Lists.
First of all, for those who don't know what median is:
Median: Median is the middle element of a sorted list. (If the given list is not ordered / sorted, then to find the median we first have to sort it). For example, to get the median of (2, 6, 7, 10, 5), we first sort the given series to (2, 6, 5, 7, 10). Then we get the middle element, or the median 5. Note, that if the set has even number of elements, then there is no exact median—in that case, we take the average of the two middle elements and consider the result as the median. For example, the median of (4, 6, 7, 9, 10, 15) is [(7+9) / 2] = 8.
Thus, a very common approach to solve this would be to merge the two given already sorted Linked Lists and, then, find out the median from the resultant bigger list. This method is simple and not efficient, because it will require too much of extra space to store the merged Linked List.
A better approach would be:
-1) Take the two starting nodes of the Linked Lists as input, let the nodes be A and B .
-2) Create a variable LenA, and set LenA = length of A list.
( as fining the length of a Linked List is very easy, I'm not describing the steps here)
-3) Create a variable LenB, and set LenB = length of B list.
-4) Create a variable LenTotal, and set LenTotal = LenA + LenB.
-5) Create two variables Middle and Temp.
-6) If, (LenTotal is ODD), then set Middle = (LenTotal + 1) / 2, Otherwise, set Middle = LenTotal / 2.
-7) Create a variable Counter, and set Counter = 0.
-8) Loop Start: While ( Counter < Middle )
-9) If (both A != NULL And B != NULL), then
-10) If, (A --> Value <= B --> Value), then
-11) set Temp = A --> Value, and set A = A -- > Next.
-12) Otherwise, set Temp = B --> Value, and set B = B -- > Next.
-13) Else If, (only A != NULL), then, set Temp = A --> Value, and set A = A -- > Next.
-14) Else, set Temp = B --> Value, and set B = B -- > Next.
-15)Loop End.
-16)Print Temp.
-17)If, (LenTotal is EVEN) , then
-18) If (both A != NULL And B != NULL), then
-19) If, (A --> Value <= B --> Value), then
-20) set Temp = A --> Value, and set A = A -- > Next.
-21) Otherwise, set Temp = B --> Value, and set B = B -- > Next.
-22) Else If, (only A != NULL), then, set Temp = A --> Value, and set A = A -- > Next.
-23) Else, set Temp = B --> Value, and set B = B -- > Next.
-24)End If.
-25)Print Temp.
This is an efficient, in-place solution. But, look carefully, steps 9-14 and steps 18-23 are identical in the above algorithm-- I expected you to find out some way to avoid this repeatation and optimize the algorithm !