使用c++设计算法将带头结点的双循环链表L就地逆置,即利用原表各结点的空间实现逆置
时间: 2023-05-11 16:05:20 浏览: 129
可以使用以下算法将带头结点的双循环链表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;
}
相关问题
设计算法将带头结点的双循环链表L就地逆置,即利用原表各结点的空间实现逆置。
算法步骤如下:
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;
}
```
设计算法将单链表L就地逆置,即利用原表各结点的空间实现逆置。
可以使用三个指针来实现单链表的就地逆置,具体算法如下:
1. 初始化三个指针:pre指向NULL,cur指向L的头结点,next指向cur的下一个结点。
2. 遍历链表,依次将cur结点的next指向pre结点,然后将pre、cur、next分别后移。具体操作如下:
a. 将cur的next指向pre:cur->next = pre;
b. 将pre、cur、next依次向后移动:pre = cur; cur = next; next = next->next;
3. 遍历完链表后,将原链表的头结点指向逆置后的尾结点。具体操作如下:
a. 将L的头结点指向pre结点:L->next = pre;
最后返回L即可。
下面是C++代码实现:
```c++
void reverseList(ListNode* head) {
ListNode* pre = NULL;
ListNode* cur = head->next;
ListNode* next = cur->next;
while (next != NULL) {
cur->next = pre;
pre = cur;
cur = next;
next = next->next;
}
cur->next = pre;
head->next = cur;
}
```
需要注意的是,这里的head是一个头结点,而不是实际存储数据的第一个结点。在遍历完链表后,head->next指向的就是逆置后的尾结点。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)