3.编写算法逆置一个带头结点的双链表。
时间: 2024-04-06 15:12:37 浏览: 43
1. 定义一个指向头结点的指针p
2. 遍历链表,将每个节点的prev和next指针互换
3. 将头结点的next指针和prev指针互换
4. 返回头结点指针p
算法实现:
```
ListNode* reverseList(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}
ListNode* p = head;
while (p != nullptr) {
ListNode* temp = p->next;
p->next = p->prev;
p->prev = temp;
p = temp;
}
ListNode* temp = head->next;
head->next = head->prev;
head->prev = temp;
return head;
}
```
相关问题
编写算法逆置一个带头结点的双链表
算法如下:
1. 定义三个指针p、q、r,分别指向当前节点、前一个节点和后一个节点。
2. 初始化p指向头结点的下一个节点,q指向头结点,r指向p的下一个节点。
3. 将头结点的next指针置为NULL。
4. 依次遍历链表中的每个节点,将p的next指针指向q,将p的prev指针指向r。
5. 将q指针指向p,将p指针指向r,将r指针指向r的下一个节点。
6. 当r指针指向NULL时,遍历结束,将头结点的next指针指向q。
代码如下:
```c++
void reverseList(Node *head)
{
Node *p = head->next;
Node *q = head;
Node *r = p->next;
head->next = NULL;
while (r != NULL)
{
p->next = q;
p->prev = r;
q = p;
p = r;
r = r->next;
}
p->next = q;
p->prev = NULL;
head->next = p;
}
```
编写算法逆置一个带头结点的双链表。
1. 如果链表为空或只有一个结点,则直接返回原链表。
2. 定义三个指针pre、p和q,分别指向当前结点的前一个结点、当前结点和当前结点的后一个结点。
3. 将当前结点的前一个结点指向当前结点的后一个结点,将当前结点的后一个结点指向当前结点。
4. 将pre指向当前结点,将当前结点指向q。
5. 重复上述过程,直到q指向空。
6. 将头结点的next指向pre,即完成逆置。
算法实现如下:
```python
def reverse_list(head):
if not head or not head.next:
return head
pre = None
p = head.next
while p:
q = p.next
p.next = pre
p.prev = q
pre = p
p = q
head.next = pre
pre.prev = head
return head
```