如何用递归函数获取链表的最小值与最大值？错误排查及修正

问题原因 #

你写的递归函数犯了一个典型错误：只调用了递归，但完全没有利用递归调用返回的结果。

拿getMin举例：

• 你初始化minValue为INT_MAX，然后和当前节点的data比较，此时minValue会变成当前节点的值（因为INT_MAX肯定比任何节点值大）。
• 接着你调用getMin(currentNode->next)，但这个调用的返回值被直接丢弃了，完全没参与后续的比较逻辑。
• 最后返回的只是当前节点和INT_MAX比较后的结果，也就是第一个节点的值，递归遍历后续节点的结果根本没起作用。

getMax的问题完全一样：初始化maxValue为INT_MIN，和当前节点比较后变成首节点值，递归调用的结果被丢弃，最终返回首节点值。

修复方案 #

递归的核心逻辑应该是：当前节点的值，与剩余链表的最值进行比较，取其中符合要求的那个。

修复后的getMin函数 #

int getMin(node *currentNode) {
    // base case：空链表，返回INT_MAX（作为比较的边界值）
    if (currentNode == NULL) {
        return INT_MAX;
    }
    // 递归获取剩余链表的最小值
    int restMin = getMin(currentNode->next);
    // 比较当前节点值和剩余链表最小值，返回更小的那个
    return min(currentNode->data, restMin);
}

修复后的getMax函数 #

int getMax(node *currentNode) {
    // base case：空链表，返回INT_MIN（作为比较的边界值）
    if (currentNode == NULL) {
        return INT_MIN;
    }
    // 递归获取剩余链表的最大值
    int restMax = getMax(currentNode->next);
    // 比较当前节点值和剩余链表最大值，返回更大的那个
    return max(currentNode->data, restMax);
}

完整修复后的程序 #

#include <bits/stdc++.h>

using namespace std;

struct node {
    int data;
    node *next;
} *root;

void append(vector<int> vec) {
    node *currentNode, *tail;
    root = new node();
    root->data = vec[0];
    root->next = NULL;
    tail = root;
    for (vector<int>::iterator i = vec.begin() + 1; i < vec.end(); i++) {
        currentNode = new node();
        currentNode->data = *i;
        currentNode->next = NULL;
        tail->next = currentNode;
        tail = tail->next;
    }
}

void display(node *currentNode) {
    if (currentNode != NULL) {
        cout << currentNode->data << " ";
        display(currentNode->next);
    }
}

int getMin(node *currentNode) {
    if (currentNode == NULL) {
        return INT_MAX;
    }
    int restMin = getMin(currentNode->next);
    return min(currentNode->data, restMin);
}

int getMax(node *currentNode) {
    if (currentNode == NULL) {
        return INT_MIN;
    }
    int restMax = getMax(currentNode->next);
    return max(currentNode->data, restMax);
}

int main() {
    vector<int> vec {5, 7, 3, 4, 6};
    append(vec);
    display(root);
    cout << "\nMin: " << getMin(root) << "\n";
    cout << "Max: " << getMax(root) << "\n";

    return 0;
}

逻辑解释 #

• Base Case：当链表为空（currentNode == NULL）时，getMin返回INT_MAX（因为空链表没有元素，任何值都比它小），getMax返回INT_MIN（任何值都比它大），这是递归的终止条件。
• 递归步骤：对于非空节点，先递归获取后续链表的最值，再将当前节点的值与这个最值比较，返回符合要求的结果。这样递归会从链表末尾开始回溯，逐步比较出整个链表的最值。

运行修复后的程序，输出会是：

5 7 3 4 6 
Min: 3
Max: 7

内容的提问来源于stack exchange，提问作者Anikul Islam