Consider a pointer pointing to first element and keep comparing with next element,
Which ever is highest put it in next node, keep moving the pointer, final element will be the the highest.
1 User has rated as useful.
Login to rate this answer.
Traverse the complete linked list K times first time find the maximum value and subsequent times find the next largest value.
In case the values are duplicate we can increment the loop counter by 1 every time we find a duplicate value of a new found nth max value.
Login to rate this answer.
int i,j,k,cnt=0;
input k
input the linked list
itr1=itr2=head;
while (itr1!=null)
{
while (itr2!=null)
{
if(itr1.info>itr2.info && itr1!=itr2)
{
cnt++;
}
}
if(cnt==N-k)
{
print itr1->info;
break;
}
cnt=0;
}
Login to rate this answer.
1. We need to traverse the list K times.
2. Take 3 pointers p1, p2 , p3.Set p1 to it
3. In first iteration find the largest element and set p1 to that element.Set p1 to it
4. In second iteration exclude the node pointed by p1 hance u will get the 2nd largest element. Set p2 to the second largest element.
5. In third iteration make use of pointer p1 exclude the elements which are greater than the element currently pointing by p2.hence u will get the 3rd largest element. Set p1 to it
6. Repeat step 5 and make alternate use of p1 p2 till the final answer.
7. P3 will be needed for comparison and iteration.
Login to rate this answer.
If the question assumes that the extra memory used should not be a function of x, then one possible solution can be the use of heap to make min-queue. After k elements have been entered , compare the next entry with the minimum of the queue. If its larger, extract-min and insert the new number.
After the whole list is complete, sort the heap to find the maximum.
Login to rate this answer.
batman
Answered On : Oct 4th, 2011
Not enough information about the data in the linked list.
Solution 1.
Assuming int & no duplicates & rather small [min,max] interval: Iterate through the list once to find the min&max. Make a binary search on the interval [min, max] to find out the V value for which there are exactly k higher values in the list(complexity log(max-min)*n). Find the Find the maximum value in the queue smaller than V and you have your answer.
You can of course make adjustments for other data types & duplicates & whatever.
Solution 2.
General double numbers
Use n0-n9 to store the number of values that start with 0-9. Find out with what number our Kth value starts, find out the new K for those numbers only. Repeat the procedure for the new numbers(they can still remain in the same list, you will just have to check their start) until you have the entire number in the 'starting with' value.
Complexity (nr of digits in the longest number - including what is after the coma) * n, extra memory 10 variables.
Login to rate this answer.
