CODEWITHSUNDEEP
javalist
broccoli lover
broccoli lover

Reputation: 33

Finding the 2nd max key of linked list?

Please help me fix my code. Some cases work but I believe cases like [9,1,2] would not work because the first number is the largest in that case. I am not sure how to fix that in my code.

public Key secondMaxKey () {
    Node max = first;
    Node max_2nd = first;

    if (size() < 2) {
        return null;
    }

    for (Node x = first; x != null;x = x.next) {

        if (x.key.compareTo(max.key) == 1) {
            max_2nd = max;
            max = x;
        } else if (x.key.compareTo(max_2nd.key) == 1) {
            max_2nd = x;
        }
    }
    return max_2nd.key;
}

Upvotes: 3

Views: 440

Answers (5)

Joe Drool
Joe Drool

Reputation: 11

public Key secondMaxKey() {
    if (this.size() <= 1)
        return null;
    if (this.size() == 2){
        if(first.key.compareTo(first.next.key) > 0){
            return first.next.key;
        }
    }
    Key max = first.key;
    Key secondMax = first.next.key;
    Node n = first;
    for (Node x = n.next; x != null; x = x.next) {
        if (x.key.compareTo(max) >= 0) {
            secondMax = max;
            max = x.key;
        } else if (x.key.compareTo(secondMax) > 0)
            secondMax = x.key;
    }
    return secondMax;
}

I believe your issue is with the implementation. particularly, setting the second max to the same temp Node as the max.

Upvotes: 1

Maciej Kowalski
Maciej Kowalski

Reputation: 26552

In my opinion you first check the size then proceed with the algorithm. A little change to yours here as we use the first two nodes to set the max and max_2 (depending on the values of these). Then we proceed as you did. Check it out. Hope it helps 

public Key secondMaxKey () {
            if(size() < 2){
                return null;
            }
            Node max = null;
            Node max_2 = null;

            Node second = first.next;

            if(first.key.compareTo(second.key) > 0){
                max = first;
                max_2 = second;
            }   else{
                max = second;
                max_2 = first;
            }

            for (Node x=second.next; x != null;x=x.next)
            {
                if (x.key.compareTo(max.key) > 0)
                {
                    max_2=max;
                    max=x;
                }
                else if ((x.key.compareTo(max_2.key) > 0)
                        && (x.key.compareTo(max.key) < 0))
                {
                    max_2=x;
                }
            }
            return  max_2.key;
        }

Upvotes: 1

Jojo John
Jojo John

Reputation: 400

Please Check below logic. I have checked with your code here and it returns second maximum (Edited as per LinkedListST in the question)

   public Key secondMaxKey () {
    Node max = first;
    Node max_2nd = null;
    Node temp = null;

    if (size() < 2) {
        return null;
    }

    for (Node x = first.next; x != null; x = x.next) {
        if (x.key.compareTo(max.key)>0) {
            temp = max;
            max = x;
            if(temp.key.compareTo(max_2nd.key)>0)
            {
                max_2nd=temp;
            }

        } else if (max_2nd == null || x.key.compareTo(max_2nd.key) > 0) {
            max_2nd = x;
        }
    }

    return max_2nd.key;
}

for example

{9,1,2}
Loop 1 (x=1) : max =9 max_2 =0 x=1 After loop max = 9 max_2 = 1
Loop 2 (x=2) : max =9 max_2 =1 x=2 After loop max = 9 max_2 = 2

Upvotes: 0

Remy Cilia
Remy Cilia

Reputation: 2623

I think you should initiate max and max_2nd with null and check if they are null in you if statements: 

public Key secondMaxKey () {
    Node max = null;
    Node max_2nd = null;

    if (size() < 2) {
        return null;
    }

    for (Node x = first; x != null; x = x.next) {
        if (max == null || x.val.compareTo(max.val) > 0) {
            max_2nd = max;
            max = x;
        } else if (max_2nd == null || x.val.compareTo(max_2nd.val) > 0) {
            max_2nd = x;
        }
    }

    return max_2nd.key;
}

Upvotes: 0

vijay
vijay

Reputation: 926

This helps you ,

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        List l=new ArrayList();
        l.add(9);
        l.add(1);
        l.add(2);

        int max2=max_2nd(l);
        System.out.println(max2);
    }
    private static int max_2nd(List l) {

        Set s= new HashSet(l);
        s.remove(Collections.max(s));
        int i =(int)Collections.max(s);
        return i;

    }
}

Upvotes: 0

Related Questions