1试写出一个采用单链表存储的线性表A（A带表头结点 Head）的数据元素逆置的算法。 •2.试写出一个将数据元素b插入到带表头结点Head的单链表中第一个元素为a的结点之前的算法（若链表中没有a，则将b插入到链表最后)。 •3.将数据元素b插入循环单链表Head中第一个数据元素为 a的结点之前。

1. 线性表A逆置算法：

1）先判断A是否为空表或只有一个结点，如果是，直接返回。

2）定义三个指针pre、p、q，分别指向表头结点、第一个数据结点和第二个数据结点。

3）将p的next指向pre，将pre指向p，将p指向q，将q指向q的next。

4）重复第3步，直到q指向NULL为止。

5）最后将Head的next指向pre，逆置完成。

2. 插入数据元素b算法：

1）先查找单链表中第一个元素为a的结点，如果找到了，记录该结点的前驱结点pre，如果没找到，则pre指向链表的尾结点。

2）创建新结点s，并将b存入s的数据域中。

3）将pre的next指向s，将s的next指向a所在结点。

3. 循环单链表插入数据元素b算法：

1）先查找循环单链表中第一个元素为a的结点，如果找到了，记录该结点的前驱结点pre，如果没找到，则pre指向循环单链表的尾结点。

2）创建新结点s，并将b存入s的数据域中。

3）将pre的next指向s，将s的next指向a所在结点。

4）如果a所在结点是循环单链表的头结点，还需要将尾结点的next指向s。

相关问题

1.试写出一个采用单链表存储的线性表A（A带表头结点 Head）的数据元素逆置的算法。

算法思路：

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为链表结点类型。

.试写出一个采用单链表存储的线性表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;
}