面试题：C++指针函数返回值在复杂数据结构中的应用

Question

假设有一个自定义的结构体 `struct Node { int data; Node* next; }`，编写一个指针函数，该函数接收一个 `Node*` 类型的链表头指针，在链表中找到数据值最大的节点，并返回指向该节点的指针。同时，要考虑链表为空的情况，并在主函数中展示如何调用这个指针函数并安全地使用返回值。

Answer 1

#include <iostream>

// 定义结构体
struct Node {
    int data;
    Node* next;
};

// 查找数据值最大的节点的函数
Node* findMaxNode(Node* head) {
    if (head == nullptr) {
        return nullptr;
    }
    Node* maxNode = head;
    Node* current = head->next;
    while (current != nullptr) {
        if (current->data > maxNode->data) {
            maxNode = current;
        }
        current = current->next;
    }
    return maxNode;
}

int main() {
    // 创建链表 1 -> 3 -> 2
    Node* head = new Node{1, new Node{3, new Node{2, nullptr}}};

    Node* maxNode = findMaxNode(head);
    if (maxNode != nullptr) {
        std::cout << "最大值节点的数据: " << maxNode->data << std::endl;
    } else {
        std::cout << "链表为空" << std::endl;
    }

    // 释放链表内存
    Node* current = head;
    while (current != nullptr) {
        Node* temp = current;
        current = current->next;
        delete temp;
    }

    return 0;
}

1. findMaxNode 函数:
   • 首先检查链表是否为空，如果为空，直接返回 nullptr。
   • 初始化 maxNode 为头节点，然后遍历链表，比较每个节点的数据值与 maxNode 的数据值，如果当前节点的数据值更大，则更新 maxNode。
   • 遍历结束后返回 maxNode。
2. main 函数:
   • 创建一个简单的链表。
   • 调用 findMaxNode 函数获取数据值最大的节点指针。
   • 检查返回值是否为 nullptr，如果不为空，输出最大值节点的数据；如果为空，输出链表为空的提示。
   • 最后释放链表占用的内存，防止内存泄漏。