学习笔记-数据结构-线性表（2024-04-24）

对不带头节点的单链表进行就地倒置

函数的处理步骤如下：
初始化三个指针 p、q 和 r。p 用于追踪新链表的最后一个节点，最初设置为 NULL。q 指向当前正在处理的原链表的节点，最初是链表的头节点。r 用于临时保存 q->next，即下一个要处理的节点。
在 while 循环中，遍历原链表。循环的每一次迭代都会处理一个节点，将其从原位置移动到新链表的前端。这通过改变节点的 next 指针实现，使其指向新链表的当前第一个节点 p。
在移动节点之后，p 更新为 q，q 更新为 r，以继续遍历和反转剩余的链表。
当 q 为 NULL 时，意味着已经处理完所有的节点，此时 p 指向新链表的头节点。最后，将链表的头指针 L 更新为 p，完成链表的反转。

typedef struct LNode
{
	Elemtype data;
	struct LNode *next;
}LNode,*LinkList;
void reverse(LinkList &L)
{
    LNode *p = NULL; // p作为新链表的头指针，初始化为NULL
    LNode *q = L;    // q为旧链表的遍历指针，初始化为L的头节点
    LNode *r = NULL; // r作为临时指针，用来保存q的下一节点

    // 遍历旧链表，直到q为NULL
    while(q != NULL)
    {
        r = q->next;  // 保存q的下一节点，因为改变链表结构后就无法通过q来访问了
        q->next = p;  // 反转指针，将q的next指向新链表的第一个节点p
        p = q;        // p向后移动，现在p是新链表的第一个节点
        q = r;        // q向后移动，q变成下一个待处理的节点
    }
    L = p; // 最后将原链表的头指针指向新链表的头节点p，完成反转
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21