C++中双指针访问链表及无循环/数组/链表实现10数最值求解

双指针绝对是C++链表操作里的「瑞士军刀」，常见的玩法有快慢指针、前后指针两种，我给你拆解清楚，结合代码一看就懂。

首先咱们先定义一个标准的链表节点结构：

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

玩法1：快慢指针找链表中点 #

快慢指针的核心逻辑是：快指针每次走2步，慢指针每次走1步，当快指针走到链表末尾时，慢指针刚好停在链表中间。这在归并排序链表、找倒数第k个节点这类场景里特别好用。

ListNode* findMiddle(ListNode* head) {
    if (!head || !head->next) return head;
    
    // 这里用head->next初始化快指针，是为了偶数个节点时返回左中点；要是用head初始化，会返回右中点，按需调整就行
    ListNode* slow = head;
    ListNode* fast = head->next;
    
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

玩法2：快慢指针判断链表是否有环 #

如果链表存在环，快指针最终会追上慢指针（就像操场跑步快的人套圈慢的）；如果没环，快指针会先走到nullptr。

bool hasCycle(ListNode* head) {
    if (!head || !head->next) return false;
    
    ListNode* slow = head;
    ListNode* fast = head->next;
    
    while (slow != fast) {
        if (!fast || !fast->next) return false;
        slow = slow->next;
        fast = fast->next->next;
    }
    return true;
}

玩法3：前后指针反转链表 #

用prev指针记录当前节点的前一个节点，curr指针遍历链表，每次把当前节点的next指向prev，然后同步更新两个指针的位置，就能实现链表反转。

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    
    while (curr) {
        ListNode* nextTemp = curr->next; // 先存下一个节点，不然反转后就找不到后续节点了
        curr->next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

这题限制挺有意思的——不能用循环、数组、链表，那咱们就得换个思路：用递归！递归本质上是用函数调用栈替代循环的迭代过程，而且可以通过参数传递来跟踪当前的最大最小值，完全不用存储所有数字。

核心思路：

• 写一个递归函数，参数包含当前已输入的数字个数、当前记录的最大值、当前记录的最小值
• 当输入次数达到10时，直接输出结果
• 否则，输入新数字，更新最大最小值后继续递归

直接上可运行的代码：

#include <iostream>

void inputAndFind(int count, int maxVal, int minVal) {
    if (count == 10) {
        std::cout << "最大值：" << maxVal << std::endl;
        std::cout << "最小值：" << minVal << std::endl;
        return;
    }
    
    int num;
    std::cout << "请输入第" << count + 1 << "个数字：";
    std::cin >> num;
    
    // 第一次输入时，直接把当前数作为初始的最大最小值
    if (count == 0) {
        inputAndFind(count + 1, num, num);
    } else {
        int newMax = (num > maxVal) ? num : maxVal;
        int newMin = (num < minVal) ? num : minVal;
        inputAndFind(count + 1, newMax, newMin);
    }
}

int main() {
    // 初始调用：count从0开始，max和min随便传，第一次输入会自动覆盖
    inputAndFind(0, 0, 0);
    return 0;
}

内容的提问来源于stack exchange，提问作者Muzahir Hussnain