用于查找符号表中第二大键的函数

Question

所以我编写了一个函数，该函数将使用链表实现在无序符号表中找到第二大键，到目前为止，我拥有的代码无法正常工作，并且想知道是否有人有任何提示谢谢！

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;
}`

输出：

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

Answer 1

你的代码接近正确。for循环中的终止条件需要检查pointer!=null，而不是pointer.next!=null。此外，如果pointer.key小于Max，则需要将其与secondMax进行比较，如果它更大，或者secondMaxnull(即尚未设置(则接受它

下面是一些代码供参考：

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;
}
}