AB15-将带头结点的单链表就地逆置（原地逆置）

代码实现

/**
 * 将带头结点的单链表就地逆置（原地逆置）
 * @param L 指向链表头结点的指针
 */
void reverse(LinkList L) {
    // p指向当前要处理的结点（从第一个数据结点开始）
    LNode* p = L->next;

    // 将头结点的指针域置空，为逆置后的新链表做准备
    L->next = NULL;

    // r指向下一个要处理的结点（临时保存）
    LNode* r;

    // 遍历原链表，逐个将结点插入到头结点之后
    while (p != NULL) {
        // 保存下一个要处理的结点
        r = p->next;

        // 将当前结点p插入到头结点之后（头插法）
        p->next = L->next;  // p指向原头结点的后继
        L->next = p;        // 头结点指向p

        // 移动到下一个要处理的结点
        p = r;
    }
}

算法执行流程图解

逆置过程示例：

原链表：L→[ ]→[1]→[2]→[3]→[4]→NULL

初始状态：
L→[ ]→NULL    [1]→[2]→[3]→[4]→NULL
 ↑             ↑
L->next=NULL   p

第1步：处理结点[1]
r = p->next = [2]
p->next = L->next = NULL
L->next = p = [1]
p = r = [2]

结果：L→[ ]→[1]→NULL    [2]→[3]→[4]→NULL

第2步：处理结点[2]
r = p->next = [3]
p->next = L->next = [1]
L->next = p = [2]
p = r = [3]

结果：L→[ ]→[2]→[1]→NULL    [3]→[4]→NULL

第3步：处理结点[3]
r = p->next = [4]
p->next = L->next = [2]
L->next = p = [3]
p = r = [4]

结果：L→[ ]→[3]→[2]→[1]→NULL    [4]→NULL

第4步：处理结点[4]
r = p->next = NULL
p->next = L->next = [3]
L->next = p = [4]
p = r = NULL

最终结果：L→[ ]→[4]→[3]→[2]→[1]→NULL

详细执行步骤图解

逆置前：L→[ ]→[A]→[B]→[C]→[D]→NULL
        ↑    ↑    ↑    ↑    ↑
       头   p1   p2   p3   p4

逆置过程：

步骤1：处理A
L→[ ]→[A]→NULL    [B]→[C]→[D]→NULL

步骤2：处理B
L→[ ]→[B]→[A]→NULL    [C]→[D]→NULL

步骤3：处理C
L→[ ]→[C]→[B]→[A]→NULL    [D]→NULL

步骤4：处理D
L→[ ]→[D]→[C]→[B]→[A]→NULL

复杂度分析

时间复杂度：O(n)

• 遍历时间：需要遍历整个链表一次，处理n个数据结点
• 每次操作：每次循环内执行常数次指针操作O(1)
• 总体时间复杂度：O(n)

空间复杂度：O(1)

• 额外空间：只使用了常数个指针变量：p、r
• 无额外存储：没有使用辅助数组或其他数据结构
• 原地操作：直接修改原链表的指针连接关系
• 算法额外空间复杂度：O(1)

优化版本：更清晰的变量命名和逻辑

/**
 * 优化版本：更清晰的变量命名和逻辑
 */
void reverse_Optimized(LinkList L) {
    if (L == NULL || L->next == NULL) {
        return;  // 空链表或只有一个头结点
    }

    // current指向当前要处理的结点
    LinkList current = L->next;

    // 将头结点断开，准备构建新链表
    L->next = NULL;

    // 逐个处理原链表中的每个结点
    while (current != NULL) {
        // 保存下一个要处理的结点
        LinkList next = current->next;

        // 头插法：将current插入到头结点之后
        current->next = L->next;
        L->next = current;

        // 移动到下一个结点
        current = next;
    }
}

递归版本：链表逆置

/**
 * 递归版本：链表逆置
 */
void reverse_Recursive(LinkList L) {
    if (L == NULL || L->next == NULL) return;

    L->next = reverseHelper(L->next);
}

// 辅助函数：递归逆置不带头结点的链表
LinkList reverseHelper(LinkList head) {
    // 基础情况：空链表或只有一个结点
    if (head == NULL || head->next == NULL) {
        return head;
    }

    // 递归逆置后面的链表
    LinkList newHead = reverseHelper(head->next);

    // 调整当前结点的指针
    head->next->next = head;
    head->next = NULL;

    return newHead;
}

算法变体：返回新头结点

/**
 * 不带头结点的链表逆置
 * @param head 原链表的第一个结点
 * @return 逆置后链表的第一个结点
 */
LinkList reverse_NoHead(LinkList head) {
    LinkList prev = NULL;    // 前驱结点
    LinkList current = head; // 当前结点

    while (current != NULL) {
        LinkList next = current->next;  // 保存后继
        current->next = prev;           // 反转指针
        prev = current;                 // 移动前驱
        current = next;                 // 移动当前
    }

    return prev;  // prev指向新的头结点
}

算法特点

核心思想： 使用头插法的思想，将原链表中的每个结点依次插入到头结点之后，实现整体逆置。

关键步骤： 1. 初始化：断开头结点与第一个数据结点的连接 2. 遍历：逐个处理原链表中的每个数据结点 3. 头插：将每个结点以头插法的方式插入到新链表中 4. 移动：处理完一个结点后移动到下一个结点

重要特性： - 原地逆置：不需要额外的存储空间 - 时间效率：只需一次遍历 - 空间效率：额外空间复杂度O(1) - 稳定性：保持所有数据不变，只改变连接关系

与数组逆置的对比：

特性	数组逆置	链表逆置
时间复杂度	O(n)	O(n)
空间复杂度	O(1)	O(1)
实现方式	双指针交换	头插法重构
访问方式	随机访问	顺序访问

这种逆置算法是链表操作中的经典算法，在实际应用中经常用于改变数据的处理顺序。