1.试写出一个采用单链表存储的线性表A(A带表头结点 Head)的数据元素逆置的算法。
时间: 2023-06-01 12:02:06 浏览: 94
算法思路:
1. 定义三个指针:p、q、r,分别指向头结点、首元结点和尾元结点;
2. 从头结点开始遍历,将p的指针域指向q的指针域,q的指针域指向r的指针域;
3. 将r指向q,q指向p的指针域;
4. 将q指向p,p指向原来的p的指针域;
5. 重复上述步骤,直到p指向NULL,此时链表逆置完成。
算法实现:
void ReverseList(LinkList &A) {
if (A == NULL || A->next == NULL) {
return;
}
ListNode *p = A, *q = A->next, *r = q->next;
while (r != NULL) {
q->next = p;
p = q;
q = r;
r = r->next;
}
q->next = p;
A->next->next = NULL;
A->next = q;
}
注:LinkList为指向链表头结点的指针类型,ListNode为链表结点类型。
相关问题
1.试写出一个采用单链表存储的线性表A(A带表头结点 Head)的数据元素逆置的算法。
可以使用三个指针,分别指向当前节点、前一个节点和后一个节点,依次将当前节点的指针指向前一个节点,直到遍历完整个链表。具体算法如下:
```
void ReverseList(ListNode* Head) {
if (Head == nullptr || Head->next == nullptr) {
return;
}
ListNode* prev = nullptr;
ListNode* curr = Head->next;
ListNode* next = nullptr;
while (curr != nullptr) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
Head->next = prev;
}
```
其中,ListNode 是链表节点的结构体,包含一个指向下一个节点的指针 next 和一个数据元素 val。Head 是链表的头节点,不存储任何数据元素,只是用来方便操作链表。
.试写出一个采用单链表存储的线性表A(A带表头结点 Head)的数据元素逆置的算法。
可以使用三个指针,分别指向当前节点、前一个节点和后一个节点,依次遍历链表并将当前节点的 next 指针指向前一个节点,然后将三个指针向后移动一个节点,直到遍历完整个链表。具体实现如下:
void reverseList(ListNode* head) {
if (head == NULL || head->next == NULL) {
return;
}
ListNode* prev = NULL;
ListNode* curr = head->next;
ListNode* next = NULL;
while (curr != NULL) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
head->next = prev;
}
阅读全文