C++怎么实现一个链表反转_C++数据结构与链表操作面试题-C++-PHP中文网

C++怎么实现一个链表反转_C++数据结构与链表操作面试题

下次还敢

发布： 2025-11-28 01:23:34

原创

922人浏览过

链表反转的核心是调整节点指针方向，迭代法用prev、curr、next三指针遍历反转，递归法先递归到底再逐层调整指针并断开原连接，需处理空节点和环问题。

c++怎么实现一个链表反转_c++数据结构与链表操作面试题

链表反转是C++数据结构中非常经典的面试题，考察对指针操作和逻辑思维的理解。实现单向链表的反转核心在于调整每个节点的指针方向，使其指向前一个节点。

定义链表节点结构

在开始之前，先定义一个简单的链表节点结构：

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

登录后复制

迭代法反转链表

最常用的方法是使用三个指针来完成反转：prev、curr、next。通过遍历链表，逐步改变指针方向。

步骤说明：

立即学习“C++免费学习笔记（深入）”；

初始化 prev = nullptr，curr 指向头节点
遍历链表，保存 curr->next 到 next
将 curr->next 指向 prev
prev 和 curr 向前移动一步
当 curr 为空时，prev 就是新的头节点

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; // 新的头节点
}

登录后复制

递归法反转链表

递归方法从后往前处理节点，思路是先反转后面的链表，再调整当前节点的连接。

小爱开放平台

小米旗下小爱开放平台

281

查看详情

关键点： 递归到尾节点后，逐层返回新头节点，并修改当前节点与其后继的关系。

ListNode* reverseList(ListNode* head) {
    if (head == nullptr || head->next == nullptr) {
        return head;
    }
    ListNode* newHead = reverseList(head->next);
    head->next->next = head; // 让下一个节点指向自己
    head->next = nullptr;    // 断开原指向，避免环
    return newHead;
}
</font>

登录后复制