sai krishna b

 Profile Answers by sai krishna b 

• Sep 16th, 2010

 

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.

djsingh

 Profile Answers by djsingh 

• Oct 27th, 2010

 

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.

Abhis3k

 Profile Answers by Abhis3k 

• Mar 2nd, 2011

 

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;

    }

Sumit Khedkar

 Profile Answers by Sumit Khedkar 

• May 27th, 2011

 

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.

Amit Jain

 Profile Answers by Amit Jain 

• Jun 9th, 2011

 

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.

batman

• 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.

Anonymous

• Jun 19th, 2017

 

It does not work when duplicate elements are present.