C++ 单链表就地逆置：详细解析与代码实现

本文将介绍如何使用 C++ 实现带头结点的单链表就地逆置（不增加额外结点）。

算法原理

实现单链表就地逆置需要使用三个指针：

prev：指向当前结点的前一个结点
cur：指向当前结点
next：指向当前结点的下一个结点

算法步骤如下：

初始化：将 prev 指向头结点，cur 指向头结点的下一个结点，next 指向 cur 的下一个结点。
迭代：使用循环遍历链表，每次将 cur 的 next 指针指向 prev，然后将 prev 指向 cur，cur 指向 next，最后更新 next 指针。
完成逆置：当 cur 指向空指针时，表示链表已逆置完成。将头结点的 next 指针指向 prev，即可完成链表逆置。

代码实现

typedef struct Node {
    int data;
    struct Node* next;
} Node, *LinkList;

void reverseList(LinkList La) {
    Node* prev = La;
    Node* cur = La->next;
    Node* next = cur->next;

    prev->next = nullptr; // 将头结点的next指针置为空

    while (cur != nullptr) {
        cur->next = prev; // 将当前结点的next指针指向前一个结点
        prev = cur; // prev指向当前结点
        cur = next; // cur指向下一个结点
        if (next != nullptr) {
            next = next->next; // next指向下一个结点的下一个结点
        }
    }

    La->next = prev; // 将头结点的next指针指向逆置后的第一个结点
}

注意

在逆置链表时，需要使用三个指针 prev、cur 和 next 来保存当前结点的前一个结点、当前结点和下一个结点，以防止指针丢失。

总结

本文详细讲解了 C++ 单链表就地逆置的算法原理，并提供了完整代码实现和注释，希望对您理解和掌握单链表逆置算法有所帮助。