试写出一个采用单链表存储的线性表的数据元素逆置的算法
时间: 2023-05-22 17:04:30 浏览: 58
可以采用遍历链表的方式,依次将每个结点的指针指向其前驱结点,从而实现链表的逆置。具体实现如下:
1. 定义一个指向链表头结点的指针p,并将其初始化为头结点的下一个结点p->next;
2. 定义3个指针pre、cur、nex,其中pre指向NULL,cur指向p,nex指向cur的下一个结点;
3. 依次遍历链表的每个结点,将cur的指针指向pre,然后pre、cur、nex向后滑动一个结点,直到nex指向NULL为止;
4. 将p指向链表的最后一个结点。
逆置代码如下:
void reverse(LinkList &L) {
if(!L || !L->next) {
return;
}
LinkList p = L->next, pre = NULL, cur = p, nex = p->next;
while(nex) {
cur->next = pre;
pre = cur;
cur = nex;
nex = nex->next;
}
cur->next = pre;
L->next = cur;
}
注意:此代码仅适用于采用头结点的单链表存储结构,如果未采用头结点,需对代码进行相应修改。
相关问题
写出一个采用单链表存储的线性表A的数据元素逆置的算法
可以使用头插法,从原链表的头节点开始,依次将每个节点插入到新链表的头部,最终得到逆置后的链表。具体实现代码如下:
void reverseList(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return;
}
ListNode* newHead = nullptr;
ListNode* cur = head;
while (cur != nullptr) {
ListNode* next = cur->next;
cur->next = newHead;
newHead = cur;
cur = next;
}
head = newHead;
}
试写出一个采用单链表存储的带表头结点head的线性表A的数据元素逆置的算法
下面是采用单链表存储的带表头结点head的线性表A的数据元素逆置的算法:
```
void ReverseList(LinkList &L) {
// 首先将头结点指针赋值为 NULL,同时用 p 指针指向头结点
LNode *p = L->next;
L->next = NULL;
// 循环遍历链表,将每个结点的 next 指针指向其前一个结点
while (p != NULL) {
LNode *tmp = p->next;
p->next = L->next;
L->next = p;
p = tmp;
}
}
```
这个算法使用了一个循环遍历链表的方法,将每个结点的 next 指针指向其前一个结点,从而实现链表的逆置。