设计算法将带头结点的双循环链表L就地逆置,即利用原表各结点的空间实现逆置。
时间: 2023-05-30 09:04:20 浏览: 166
写一个算法将一单链表逆置。要求操作在原链表上进行。
算法步骤如下:
1. 如果链表L为空或只有一个结点,则直接返回。
2. 定义三个指针prev、p和next,分别指向原链表中相邻的三个结点。
3. 将prev指针指向L的头结点,p指针指向头结点的下一个结点。
4. 进入循环,判断p是否指向头结点。如果是,则退出循环;否则执行以下步骤:
1. 将next指针指向p的下一个结点。
2. 将p的next指针指向prev。
3. 将prev指针指向p。
4. 将p指针指向next。
5. 将头结点的next指针指向prev,完成链表逆置。
具体实现代码如下:
```c
void ReverseList(DLinkList L) {
if (L == NULL || L->next == L) {
return;
}
DLinkList prev = L, p = L->next, next;
while (p != L) {
next = p->next;
p->next = prev;
prev = p;
p = next;
}
L->next = prev;
prev->prior = L;
}
```
阅读全文