使用c++设计算法将带头结点的双循环链表L就地逆置,即利用原表各结点的空间实现逆置
时间: 2023-05-11 10:05:20 浏览: 182
数据结构与算法 c++实现 //删除顺序递增表中的重复元素 //对单链表实现就地逆置 //删除递增单链表中的重复元素
5星 · 资源好评率100%
可以使用以下算法将带头结点的双循环链表L就地逆置:
1. 定义三个指针p、q、r,分别指向头结点、第一个结点和第二个结点。
2. 将p指向第一个结点,q指向第二个结点,r指向第三个结点。
3. 依次将q的next指针指向p,p的prior指针指向q,p指向q,q指向r,r指向r的next结点。
4. 重复步骤3,直到r指向头结点为止。
以下是实现代码:
void ReverseList(DLinkList L) {
if (L == NULL || L->next == L) {
return;
}
DLinkList p = L->next;
DLinkList q = p->next;
DLinkList r = q->next;
while (q != L) {
q->next = p;
p->prior = q;
p = q;
q = r;
r = r->next;
}
q->next = p;
p->prior = q;
}
阅读全文