将一个带头结点的数据域依次为 a1,a2,...,an(n≥3)的单链表的所有结点逆置, 即第一个结点的数据域变为 an,...,最后一个结点的数据域为 a1。c语言编程实现以上功能要求。
时间: 2024-03-05 09:48:30 浏览: 47
可以使用三个指针分别指向当前遍历到的结点、该结点的前驱结点和该结点的后继结点,然后依次将当前结点的 next 指针指向前驱结点,然后将三个指针向后移动一个结点,循环直到遍历完整个链表。最后将原来的头结点指向新的尾结点即可。
下面是具体的代码实现:
```
void reverseList(Node* head) {
if(head == NULL || head->next == NULL) {
return;
}
Node *prev = NULL, *cur = head->next, *next = cur->next;
while(next != NULL) {
cur->next = prev;
prev = cur;
cur = next;
next = next->next;
}
cur->next = prev;
head->next = cur;
}
```
其中,Node 表示链表的结构体,包含数据域和指向下一个结点的指针 next。head 表示头结点,head->next 指向第一个数据结点。
相关问题
将一个带头结点的数据域依次为 a1,a2,...,an(n≥3)的单链表的所有结点逆置,即第一个 结点的数据域变为 an,...,最后一个结点的数据域为 a1。c语言编程实现以上功能要求。
以下是实现此功能的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int data;
struct node *next;
} Node, *LinkedList;
LinkedList createList(int n) {
LinkedList head = (LinkedList)malloc(sizeof(Node));
head->next = NULL;
LinkedList p = head;
int i;
for (i = 1; i <= n; i++) {
LinkedList newNode = (LinkedList)malloc(sizeof(Node));
newNode->data = i;
newNode->next = NULL;
p->next = newNode;
p = p->next;
}
return head;
}
void printList(LinkedList head) {
LinkedList p = head->next;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
void reverseList(LinkedList head) {
if (head == NULL || head->next == NULL || head->next->next == NULL) {
return;
}
LinkedList p = head->next;
LinkedList q = p->next;
p->next = NULL;
while (q != NULL) {
LinkedList temp = q->next;
q->next = p;
p = q;
q = temp;
}
head->next = p;
}
int main() {
LinkedList list = createList(5);
printf("Original list: ");
printList(list);
reverseList(list);
printf("Reversed list: ");
printList(list);
return 0;
}
```
这里我们首先定义了一个数据结构 `Node` 表示链表的结点,然后使用 `typedef` 定义了一个指向 `Node` 的指针类型 `LinkedList`,方便后面的代码书写。
接着,我们实现了 `createList()` 函数来创建一个单链表,该函数接受一个整数参数 n,表示链表的长度,返回创建好的链表头结点。
我们还实现了 `printList()` 函数来打印链表中的所有结点。
最后,我们实现了 `reverseList()` 函数来实现题目所要求的功能,即将链表中的所有结点逆序。该函数使用了双指针技巧,将链表中的每个结点的指针方向进行反转。
在 `main()` 函数中,我们先创建了一个长度为 5 的链表,然后分别打印原始链表和逆序后的链表。
C语言将一个带头结点的数据域依次为 a1,a2,…,an(n≥3)的单链表的所有结点逆置,即第一个 结点的数据域变为 an,…,最后一个结点的数据域为 a1。编程实现以上功能要求
可以按照以下步骤来实现单链表的逆置:
1. 遍历链表,统计链表的长度 n,并记录链表的尾节点。
2. 新建一个空节点,作为逆置后的链表的头结点。
3. 从头结点开始遍历原链表,依次将每个节点插入到新链表的头部。
4. 将新链表的头结点指向最后一个节点,将原链表的尾节点指向空节点。
下面是具体的 C 语言代码实现:
```c
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int data;
struct node *next;
}Node, *LinkList;
//创建带头结点的单链表
LinkList createList(int n) {
LinkList head = (LinkList)malloc(sizeof(Node));
head->next = NULL;
LinkList tail = head;
for(int i=0; i<n; i++) {
LinkList p = (LinkList)malloc(sizeof(Node));
scanf("%d", &p->data);
p->next = NULL;
tail->next = p;
tail = p;
}
return head;
}
//逆置单链表
LinkList reverseList(LinkList head) {
LinkList p = head->next;
LinkList newHead = (LinkList)malloc(sizeof(Node));
newHead->next = NULL;
while(p) {
LinkList q = p->next;
p->next = newHead->next;
newHead->next = p;
p = q;
}
head->next = newHead->next;
return head;
}
//遍历单链表
void traverseList(LinkList head) {
LinkList p = head->next;
while(p) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
int main() {
int n;
printf("请输入单链表的长度:");
scanf("%d", &n);
LinkList head = createList(n);
printf("原链表为:");
traverseList(head);
head = reverseList(head);
printf("逆置后的链表为:");
traverseList(head);
return 0;
}
```
运行结果如下:
```
请输入单链表的长度:5
1 2 3 4 5
原链表为:1 2 3 4 5
逆置后的链表为:5 4 3 2 1
```
相关推荐
![](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)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)