c++中如何实现链表的反转_c++迭代与递归反转单链表方法【实例】_技术教程

迭代法用prev、curr、next三指针，先保存next再反转，返回prev；递归法以子链表新头为返回值，需断原链并重连，注意空指针与成环。

用迭代法反转单链表：三指针是核心

迭代反转的关键在于维护三个指针：prev、curr、next，避免在修改 curr->next 时丢失后续节点。常见错误是先改 curr->next 再取 next，导致链表断裂。

适用场景：空间受限、链表很长、需稳定 O(1) 额外空间。

prev 初始为 nullptr，表示新链表的尾（即原链表反转后的头的前驱）
每次循环前必须先保存 curr->next 到 next，再执行 curr->next = prev
最后返回 prev，不是 curr（此时 curr 已为 nullptr）

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    while (curr != nullptr) {
        ListNode* next = curr->next;  // 先存后继
        curr->next = prev;            // 反转当前边
        prev = curr;                  // prev 前移
        curr = next;                  // curr 前移
    }
    return prev;  // 新头节点
}

用递归法反转单链表：理解“子问题返回的是新头”

递归写法简洁，但容易误解返回值含义——reverseList(head->next) 返回的是以 head->next 为起点的子链表反转后的**新头节点**，不是原尾节点。常见错误是试图用递归函数直接操作 head 的 next 而忽略断链与重连顺序。

适用场景：代码可读性优先、链表深度可控（避免栈溢出）。

递归终止条件是 head == nullptr || head->next == nullptr，后者保证至少有一个节点可返
递归调用后，head->next 已指向新链表尾部，需让 head->next->next = head 完成翻转
必须置 head->next = nullptr，否则形成环（尤其原链表长度 ≥ 2 时）

ListNode* reverseList(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode* newHead = reverseList(head->next);
    head->next->next = head;
    head->next = nullptr;
    return newHead;
}