针对线性表的单链表存储结构,编写算法实现逆置。
时间: 2024-01-29 15:46:42 浏览: 76
实现单链表的逆置,可以采取以下步骤:
1. 定义三个指针变量p、q和r,初始时p指向头结点,q指向第一个数据结点,r指向q的后继结点;
2. 将q的next指针指向p,即将q结点插入到头结点之后;
3. 将p指向q,将q指向r,将r指向q的后继结点,即p指向q,q指向下一个结点,r指向下一个结点的下一个结点;
4. 重复步骤2和3,直到r为NULL,即所有结点都逆置完成。
下面是完整的算法实现:
```c
void ReverseList(LinkList *L) {
if (*L == NULL || (*L)->next == NULL) {
return;
}
// 定义三个指针变量
LinkList p = *L, q = (*L)->next, r = q->next;
// 头结点的next指向NULL
p->next = NULL;
while (r != NULL) {
// 将q的next指针指向p,即将q结点插入到头结点之后
q->next = p;
// 将p指向q,将q指向r,将r指向q的后继结点
p = q;
q = r;
r = r->next;
}
q->next = p;
*L = q;
}
```
其中,LinkList是指向单链表结点的指针类型,定义如下:
```c
typedef struct LNode {
int data;
struct LNode *next;
} LNode, *LinkList;
```
阅读全文