CODEWITHSUNDEEP
javalinked-listkey-valuesymbol-table
Sam M
Sam M

Reputation: 13

Function to find the second largest key in a symbol table

so im writing a function that will find the second largest key in an un-ordered symbol table using a linked list implementation, the code I have so far isnt working right and was wondering if someone had any tips thanks! 

public Key secondLargestKey () {
          if(first == null) return null;
          if(size()<=1)  return null;
          Node secondMax=null;
          Node Max=first;
           for (Node pointer=first.next;pointer.next!=null;pointer=pointer.next) {
              if(Max.key.compareTo(pointer.key)<=0) {
                 secondMax=Max;
                 Max=pointer.next; 
               }
              else {
                 secondMax=Max.next;
                 Max=pointer; 
              }

              }   
            return Max.key;
        }`

Output:

secondLargestKeyTest: Correct  String  Answer: null
secondLargestKeyTest: Correct  String A Answer: null
secondLargestKeyTest: *Error*  String AB Expected A Actual: B
secondLargestKeyTest: Correct  String ABC Actual: B
secondLargestKeyTest: Correct  String ABABABC Actual: B
secondLargestKeyTest: *Error*  String ZAYBXC Expected Y Actual: Z

Upvotes: 1

Views: 372

Answers (1)

RaffleBuffle
RaffleBuffle

Reputation: 5455

Your code is close to being correct. The terminating condition in your for loop needs to check that pointer!=null, not pointer.next!=null. Also, if pointer.key is less than Max, you then need to compare it to secondMax, and accept it if it's greater, or secondMax is null (i.e. not yet set)

Here's some code for reference: 

static <E extends Comparable<E>> E secondMax(Node<E> head)
{
  if(head == null) return null;

  E max2 = null;
  E max1 = head.key;
  for(Node<E> curr=head.next; curr!=null; curr=curr.next)
  {
    if(curr.key.compareTo(max1) >= 0)
    {
      max2 = max1;
      max1 = curr.key;
    }
    else if(max2 == null || curr.key.compareTo(max2) > 0)
    {
      max2 = curr.key;
    }
  }
  return max2;
}

static class Node<E>
{
  E key;
  Node<E> next;
  public Node(E k)
  {
    key = k;
  }
}

Upvotes: 1

Related Questions