建立一个单链表,实现倒置
时间: 2024-06-12 13:08:48 浏览: 15
建立一个单链表并实现倒置的算法可以使用头插法。下面是代码示例:
```
#include <stdio.h>
#include <stdlib.h>
#include "Untitled1.h"
void reverse(linklist head) {
linklist p, q;
p = head->next; // 保存第一个元素结点的值,从此处开始
q = NULL;
head->next = NULL; // 使头结点与链表断开
while (p) {
q = p->next; // 因为p结点的位置在后面会发生变化,所以用q保存p下一个结点地址
p->next = head->next; // 将结点插到第一个元素结点的后面
head->next = p; // 将头结点指向第一个元素结点
p = q; // p往后移动一位
}
return head;
}
```
相关问题
用c语言写一个单链表的倒置方法
好的,这个问题属于编程问题,我可以回答。以下是用C语言实现单链表倒置的方法:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点的结构体
typedef struct node {
int data;
struct node* next;
} Node, *pNode;
// 创建链表
pNode createList(int n) {
int i;
pNode head, p, q;
head = (pNode)malloc(sizeof(Node));
head->next = NULL;
q = head;
for (i = 0; i < n; i++) {
p = (pNode)malloc(sizeof(Node));
scanf("%d", &p->data);
p->next = NULL;
q->next = p;
q = p;
}
return head;
}
// 打印链表
void printList(pNode head) {
pNode p = head->next;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
// 倒置链表
pNode reverseList(pNode head) {
pNode p, q, r;
p = head->next;
q = NULL;
while (p != NULL) {
r = p->next;
p->next = q;
q = p;
p = r;
}
head->next = q;
return head;
}
int main() {
int n;
pNode head, p, q;
printf("请输入节点个数n:");
scanf("%d", &n);
head = createList(n);
printf("原始列表:");
printList(head);
head = reverseList(head);
printf("倒置后的列表:");
printList(head);
return 0;
}
```
通过这段程序,可以输入一个单链表,并将其倒置后输出。
把一个带头结点的单链表的倒置
可以通过迭代或递归的方式来实现单链表的倒置。以下是迭代的方法:
```
void reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* curr = head;
while (curr != nullptr) {
ListNode* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
head = prev; // 最后prev指向原链表的最后一个结点,即新链表的头结点
}
```
其中,`prev`指向新链表的尾结点,`curr`指向原链表的当前结点,`next`表示原链表中`curr`的下一个结点。每次将`curr`的`next`指针指向`prev`,然后将`prev`和`curr`都向后移动一位,直到`curr`为空,此时新链表的头结点就是`prev`。
如果要进行递归实现,可以采用类似于归并排序的思想,将链表不断拆分为更小的子链表,然后对子链表进行倒置,最后将所有子链表的倒置结果合并。具体实现可以参考以下代码:
```
ListNode* reverseList(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}
ListNode* tail = head->next;
ListNode* newHead = reverseList(head->next);
tail->next = head;
head->next = nullptr;
return newHead;
}
```
其中,`head`为当前子链表的头结点,`tail`为当前子链表的尾结点。递归结束条件是当前子链表为空或只有一个结点,此时返回头结点即可。在递归返回时,将当前子链表的尾结点的`next`指向当前子链表的头结点,然后将头结点的`next`设为`nullptr`,这样就完成了单链表的倒置。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![](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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)