完成单链表就地逆置算法。就地逆置只利用单链表上的结点，不再开辟新的存储空间，完成算法。（参考头插法建立单链表的算法）
输入说明：第一行先输入一个数 m，第二行再输入 m 个单链表的节点数据。
输出说明：输出就地逆置后的单链表，一个数据为一行。
平台会对你编写的代码进行测试：
输入样例：
5
1 2 3 4 5
输出样例：
5
4
3
2
1
补全如下代码
#include <stdio.h>
#include <stdlib.h>
struct Node //节点
{
int data;
struct Node *next;
};
struct LinkList //表头
{
struct Node *first;
};
void initLinkList(struct LinkList *list, int a[], int n)
{
struct Node *r, *s;
int i;
list->first = (struct Node *)malloc(sizeof(struct Node)); //附设头结点
//尾插法在单链表中插入n个数据
/***********Begin***********/
/************End************/
}
void printList(struct LinkList *list)
{
struct Node *p = list->first->next;
while(p)
{
printf("%d\n", p->data);
p = p->next;
}
}
void reverse(struct LinkList *list)
{
//完成单链表就地逆置
/***********Begin***********/
/************End************/
}
void deleteLinkList(struct LinkList *list)
{
struct Node *p = list->first, *s;
while(p)
{
s = p;
p = p->next;
free(s);
}
}
int main()
{
int m,i,x;
struct LinkList la;
scanf("%d", &m);
int a[m];
for(i = 0; i < m; i++)
{
scanf("%d", &a[i]);
}
initLinkList(&la, a, m);
reverse(&la);
printList(&la);
deleteLinkList(&la);
return 0;
}
临时节点做缓存，节点按照头插法重新插入链表即可，代码如下：
#include <stdio.h>
#include <stdlib.h>
struct Node //节点
{
int data;
struct Node *next;
};
struct LinkList //表头
{
struct Node *first;
};
void initLinkList(struct LinkList *list, int a[], int n)
{
struct Node *r, *s;
int i;
list->first = (struct Node *)malloc(sizeof(struct Node)); //附设头结点
//尾插法在单链表中插入n个数据
/***********Begin***********/
r = list->first;
for(i=0;i<n;i++)
{
s = (struct Node *)malloc(sizeof(struct Node));
s->data = a[i];
s->next = NULL;
r->next = s;
r = s;
}
/************End************/
}
void printList(struct LinkList *list)
{
struct Node *p = list->first->next;
while(p)
{
printf("%d\n", p->data);
p = p->next;
}
}
void reverse(struct LinkList *list)
{
//完成单链表就地逆置
/***********Begin***********/
struct Node* p = list->first->next;
struct Node* t;
list->first->next = NULL;
while(p)
{
t = p->next;
p->next = list->first->next;
list->first->next = p;
p = t;
}
/************End************/
}
void deleteLinkList(struct LinkList *list)
{
struct Node *p = list->first, *s;
while(p)
{
s = p;
p = p->next;
free(s);
}
}
int main()
{
int m,i,x;
struct LinkList la;
scanf("%d", &m);
int a[m];
for(i = 0; i < m; i++)
{
scanf("%d", &a[i]);
}
initLinkList(&la, a, m);
reverse(&la);
printList(&la);
deleteLinkList(&la);
return 0;
}
【以下回答由 GPT 生成】
#include <stdio.h>
#include <stdlib.h>
struct Node //节点
{
int data;
struct Node *next;
};
struct LinkList //表头
{
struct Node *first;
};
void initLinkList(struct LinkList *list, int a[], int n)
{
struct Node *r, *s;
int i;
list->first = (struct Node *)malloc(sizeof(struct Node)); //附设头结点
list->first->next = NULL; // 设置表尾指针为空
r = list->first;
for(i=0; i<n; i++) {
s = (struct Node *)malloc(sizeof(struct Node));
s->data = a[i];
r->next = s;
r = s;
}
r->next = NULL;
}
void printList(struct LinkList *list)
{
struct Node *p = list->first->next;
while(p)
{
printf("%d\n", p->data);
p = p->next;
}
}
void reverse(struct LinkList *list)
{
struct Node *p, *q;
if(list->first->next != NULL) {
p = list->first->next; // 指向第一个节点
q = p->next; // 指向第二个节点
p->next = NULL; // 第一个节点变为尾节点
while(q != NULL) {
list->first->next = q; // 将第二个节点放在链表头部
q = q->next; // 将q指向下一个节点
list->first->next->next = p; // 将p作为新的第一个节点
p = list->first->next; // p移动到第一个节点
}
}
}
void deleteLinkList(struct LinkList *list)
{
struct Node *p = list->first, *s;
while(p)
{
s = p;
p = p->next;
free(s);
}
}
int main()
{
int m, i, x;
struct LinkList la;
scanf("%d", &m);
int a[m];
for(i=0; i<m; i++) {
scanf("%d", &a[i]);
}
initLinkList(&la, a, m);
reverse(&la);
printList(&la);
deleteLinkList(&la);
return 0;
}
代码说明:
initLinkList 函数中，我们在头结点后面插入了链表的数据节点，使用尾插法将数据插入到单链表中。reverse 函数中，我们使用两个指针 p 和 q 来进行逆置操作。这两个指针分别指向前一个节点和当前节点，通过逐个改变节点的 next 指针来完成逆置操作。main 函数中，我们获取输入数据并调用函数进行逆置操作，然后输出链表数据。最后通过 deleteLinkList 函数释放链表的内存空间。【相关推荐】