C++ 单链表就地逆置算法实现及代码详解

C++ 单链表就地逆置算法实现及代码详解

本文将详细介绍 C++ 中单链表就地逆置算法的实现方法，并提供完整的代码示例。

算法思路

1. 首先判断链表是否为空，如果为空则直接返回。
2. 定义三个指针变量 pre、p 和 next，分别指向当前结点的前驱结点、当前结点和当前结点的后继结点。
3. 将头结点的 next 指针置为空，表示逆置后的链表的尾结点。
4. 从第一个结点开始，依次将当前结点的 next 指针指向其前驱结点。
5. 更新 pre、p 和 next 指针的值，继续遍历。
6. 重复步骤 4 和步骤 5，直到遍历到链表的最后一个结点。
7. 将链表的头指针指向原链表的尾结点，完成链表的逆置。

代码实现

void reverseList(LinkList La) {
    if (La.head->next == NULL) {
        return;
    }

    LNode* pre = NULL;
    LNode* p = La.head->next;
    LNode* next = p->next;

    La.head->next = NULL;

    while (p != NULL) {
        next = p->next;
        p->next = pre;
        pre = p;
        p = next;
    }

    La.head->next = pre;
}

代码解析

1. 判断链表是否为空: if (La.head->next == NULL) 判断链表是否为空，如果为空则直接返回。
2. 初始化指针: pre = NULL, p = La.head->next, next = p->next 初始化三个指针，pre 指向 NULL，p 指向第一个结点，next 指向第二个结点。
3. 设置尾结点: La.head->next = NULL 将头结点的 next 指针置为空，表示逆置后的链表的尾结点。
4. 循环遍历: while (p != NULL) 循环遍历链表，直到 p 指针指向 NULL。
5. 更新指针: next = p->next, p->next = pre, pre = p, p = next 更新三个指针的值，实现当前结点 p 指针指向其前驱结点 pre 的操作。
6. 设置头结点: La.head->next = pre 将链表的头指针指向原链表的尾结点，完成链表的逆置。

总结

本文详细讲解了 C++ 中单链表就地逆置算法的实现方法，并提供了完整的代码示例。通过三个指针变量 pre、p 和 next，循环遍历链表，将每个结点的 next 指针指向其前驱结点，最终完成链表的逆置。该算法的空间复杂度为 O(1)，时间复杂度为 O(n)，非常高效。