我们正在尝试查找链接列表的最小值

Question

我们正在练习考试，并试图在java中找到链表的最小值。该算法不断返回列表的最后一个元素，而不是最小值。

public class minMax {
element head;
public void MinMax(){
this.head = null;
}
public void addElement(element el){
element reference = this.head;
this.head = el;
element nxt = this.head.getNext();
nxt= reference;
}
public int findMin(){
int min = this.head.getValue();
element current = this.head;
while (current != null) {
if(current.getValue() < min){
System.out.println("found min");
min = current.getValue();
}
current = current.getNext();
}
return min;
}
public static void main(String[] args) {
element a = new element(5,null);
element b = new element(55, null);
element c = new element(45, null);
minMax list= new minMax();
list.addElement(a);
list.addElement(b);
list.addElement(c);
int min = list.findMin();
System.out.println(min);
}
}

Answer 1

主要问题是这个部分：

element nxt = this.head.getNext();
nxt= reference;

这不会以您期望的方式更改head中next的值。它只是使nxt变量引用reference。

您还没有包含Element类的代码，但您可能想直接更新next，例如

this.head.setNext(reference);

还有这一行：

public void MinMax() {

并没有像您所期望的那样为类定义构造函数，因为名称MinMax的大小写与类minMax的名称不同。构造函数也没有返回类型，因此要修复此问题，请重命名类MinMax(遵循Java命名约定(，然后从构造函数定义中删除void。

Answer 2

基于您的演示，我只是在本地进行了测试并进行了一些修改。

• 使用Comparable可以让你轻松地替换类型，只要类型实现了Comparable接口(要找到最小值，你必须进行比较(
• 使用head作为哨兵，使adding和deleting(如果需要删除(更容易

顺便说一句，在java中，类名最好使用Uppercase前缀，所以类名element应该替换为Element。实际上，作为一个初学者，你正在以一种很好的方式封装你的课程。

这是代码：

public class HelloWorld {
Node head; // not store any value, just used to link the nodes;
public Comparable findMin() {
if (head == null || head.next == null) {
return null;
}
Comparable min = head.next.value;
Node p = head.next.next;
while(p != null) {
if (min.compareTo(p.value) > 0) min = p.value;
p = p.next;
}
return min;
}
public void add(Node node) {
if (head == null) {
head = new Node(null, node);
} else {
node.next = head.next;
head.next = node;
}
}
public static void main(String... args) {
HelloWorld list = new HelloWorld();
list.add(new Node(5, null));
list.add(new Node(45, null));
list.add(new Node(55, null));
System.out.println(list.findMin().toString());
}
static class Node {
Comparable value;
Node next;
public Node(Comparable theValue, Node theNext) {
this.value = theValue;
this.next = theNext;
}
}
}

输出如您所期望的那样工作。

5

希望它能帮助你~