编写算法逆置一个带头结点的双链表。
时间: 2024-04-06 22:08:53 浏览: 17
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
```
相关问题
编写算法逆置一个带头结点的双链表
算法步骤如下:
1. 如果链表为空或者只有一个节点,则直接返回原链表。
2. 定义三个指针p、q、r,分别指向头结点、第一个节点、第二个节点。
3. 将第一个节点的前驱指针和后继指针都置为空,作为逆置后的最后一个节点。
4. 依次将q节点的后继指向p节点,p节点的前驱指向q节点,r节点的前驱指向q节点,q节点的后继指向r节点。
5. 将p指针指向q节点,q指针指向r节点,r指针指向r节点的后继节点。
6. 如果r指针不为空,则重复执行步骤4和步骤5,直到r指针为空为止。
7. 将头结点的前驱指针置为空,将逆置后的最后一个节点的后继指针指向头结点,将头结点的后继指针指向逆置后的第一个节点。
8. 返回逆置后的链表。
以下是算法的C++实现代码:
```c++
struct ListNode {
int val;
ListNode *prev;
ListNode *next;
ListNode(int x) : val(x), prev(NULL), next(NULL) {}
};
ListNode* reverseList(ListNode* head) {
if (!head || !head->next) {
return head;
}
ListNode *p = head, *q = head->next, *r = q->next;
p->next = NULL;
while (r) {
q->next = p;
p->prev = q;
r->prev = q;
p = q;
q = r;
r = r->next;
}
q->next = p;
p->prev = q;
head->prev = NULL;
head->next = q;
return head;
}
```
编写算法逆置一个带头结点的双链表代码c++
以下是逆置一个带头结点的双链表的C++代码:
```c++
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode* prev;
ListNode(int x) : val(x), next(NULL), prev(NULL) {}
};
ListNode* reverseList(ListNode* head) {
if (head == NULL || head->next == NULL) {
return head;
}
ListNode* curr = head->next;
ListNode* prev = NULL;
while (curr != NULL) {
ListNode* next = curr->next;
curr->next = prev;
curr->prev = next;
prev = curr;
curr = next;
}
head->next = prev;
head->next->prev = NULL;
return head;
}
int main() {
ListNode* head = new ListNode(-1);
ListNode* tail = head;
for (int i = 1; i <= 5; i++) {
ListNode* node = new ListNode(i);
tail->next = node;
node->prev = tail;
tail = node;
}
cout << "Original list: ";
ListNode* curr = head->next;
while (curr != NULL) {
cout << curr->val << " ";
curr = curr->next;
}
cout << endl;
head = reverseList(head);
cout << "Reversed list: ";
curr = head->next;
while (curr != NULL) {
cout << curr->val << " ";
curr = curr->next;
}
cout << endl;
return 0;
}
```
这里使用了双指针法,通过一个 `prev` 指针和一个 `curr` 指针来逆置链表。同时需要注意一些细节,比如链表头结点的处理和指针的赋值顺序等。