设置一个算法,将结点数据域12345的一个单链表的所有结点逆置,即第一的结点的数据域变成5,最后一个结点的数据变为1。打印输出
时间: 2023-04-25 09:01:47 浏览: 78
可以使用三个指针来实现单链表的逆置,具体步骤如下:
1. 定义三个指针:p、q、r,分别指向当前结点、前一个结点和后一个结点。
2. 将p指向链表的第一个结点,q指向NULL。
3. 循环遍历链表,每次将p的next指针指向q,然后将q、p、r三个指针向后移动一个结点。
4. 当p指向NULL时,说明已经遍历完整个链表,此时链表已经逆置完成。
5. 打印输出逆置后的链表。
具体代码如下:
void reverseList(Node* head) {
Node *p, *q, *r;
p = head;
q = NULL;
while (p != NULL) {
r = p->next;
p->next = q;
q = p;
p = r;
}
head = q;
// 打印输出逆置后的链表
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
}
相关问题
1.设计一个算法,将带头结点的数据域依次为a1,a2…an的单链表的所有结点逆置,即第1个结点的数据域变为an,第2个结点的数据域变为an-1…最后一个结点的数据域为a1 。要求算法的时间复杂度为O(n);c语言
可以使用头插法来实现单链表的逆置。具体的步骤如下:
1. 定义一个新的头结点newHead,并让它的next指针指向原链表的头结点head。
2. 定义一个指针p,初始时指向原链表的第一个结点head->next。
3. 定义一个指针q,初始时指向p->next。
4. 将p的next指针指向newHead的next指针所指向的结点,即p->next = newHead->next。
5. 将newHead的next指针指向p,即newHead->next = p。
6. 将p指针后移,指向q所指向的结点,即p = q。
7. 如果p不为空,则重复步骤3~6,否则逆置结束。
代码实现如下:
```
void reverseList(ListNode* head) {
ListNode* newHead = (ListNode*)malloc(sizeof(ListNode));
newHead->next = head;
ListNode* p = head->next;
while (p != NULL) {
ListNode* q = p->next;
p->next = newHead->next;
newHead->next = p;
p = q;
}
head->next = newHead->next;
free(newHead);
}
```
时间复杂度为O(n),因为需要遍历整个链表一次。
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为链表结点类型。
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![ppt](https://img-home.csdnimg.cn/images/20210720083527.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)