Java 链表 maxElement 递归

Question

我从事一项作业已经有一段时间了，现在我必须定义的方法之一是在列表中查找最大元素的递归解决方案。我觉得我的解决方案很接近，但我一直在插入最后一个元素，而不是最大元素。有人可以指出我需要做什么来解决这个问题吗？ * 我被指示不要使用预先构建的类或方法。 *

        int maxElement () {

    if (head == null) {
        return -1;
    }
    else {
        Node current = head;
        return maxElement (current);
    }
}

private int maxElement (Node current) {     
    Node max;
    // If our next node does not exist, our current node has to be max
    if (current.getNext() == null) {
        return current.getKey();
    }
    //  
    else {  

        if (current.getNext().getKey() > current.getKey()) {
            // Assign the larger key as our new max
            max = current.getNext();
            return maxElement (max);
        }
        else {

        }
    }
    return maxElement (max.getNext());
}

Answer 1

您必须在递归中跟踪当前最大值：

public Node max() {
    return maxAux(root, null);
}

private Node maxAux(Node current, Node currentMax) {
    if(current == null) {
        return currentMax;
    }
    if(currentMax == null || current.getKey() > currentMax.getKey()) {
        return maxAux(current.getNext(), current);   // current is the new max
    } else {
        return maxAux(current.getNext(), currentMax);
    }
}

Answer 2

这是一个相当优雅的解决方案：

public Node max(Node node1, Node node2) {
    if (node1 == null || node2 == null)
        return node1;
    else
        return max(node1.getKey() > node2.getKey() ? node1 : node2, node2.getNext());
}

使用max(head, head.getNext())调用。

如果您特别需要避免将当前最大值传递给方法，则：

private static Node currentMax;

private Node maxElement(Node node) {
    if (currentMax == null || node == null)
        return currentMax;
    else if (node.getKey() > currentMax.getKey())
        currentMax = node;
    return maxElement(node.getNext());
}

这是用 currentMax = head; 然后 maxElement(head) 调用的。

Answer 3

private Node head, max;

int maxElement () {

    if (head == null) {
        return -1;
    }
    else {
        Node current = head;
        return maxElement (current);
    }
}

    private int maxElement (Node current) {     

        // If our next node does not exist, our current node has to be max
        if (current.getNext() == null) {
            current = this.max;
            return this.max.getKey();
        }
        //  
        else {  

        if (current.getNext().getKey() > current.getKey()) {
            // Assign the larger key as our new max
            this.max = current.getNext();
            return maxElement (current.getNext());
        }
        else {

        }
    }
    return maxElement (max.getNext());
}

Java 链表 maxElement 递归

Java Linked List maxElement recursive

java

recursion

linked-list