用C语言完成题目内容:一个单链表L=(a1 , a2 , … , an-1 , an),其逆单链表定义为L’=( an , an-1 , … , a2 , a1),编写算法将单链表L逆置,要求逆单链表仍占用原单链表的空间。 输入格式:一行内输入原单链表中的数据(若干个正整数,之间用空格隔开,并以-1结束) 输出格式:一行内输出建立的原单链表数据结果,之间用两个分隔符 -- 隔开,结束标志-1不输出。 下一行内输出逆置后的单链表数据结果,之间用两个分隔符 -- 隔开。 输入样例:2 4 6 8 10 -1 输出样例:--2--4--6--8--10 --10--8--6--4--2
时间: 2024-01-12 07:03:16 浏览: 77
以下是用C语言实现该算法的代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct ListNode {
int val;
struct ListNode *next;
} ListNode;
ListNode* reverseLinkedList(ListNode *head) {
ListNode *prev = NULL, *curr = head;
while (curr) {
ListNode *next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
int main() {
// 输入原单链表数据
int val;
ListNode *dummy = (ListNode*)malloc(sizeof(ListNode));
ListNode *tail = dummy;
while (scanf("%d", &val) != EOF && val != -1) {
tail->next = (ListNode*)malloc(sizeof(ListNode));
tail = tail->next;
tail->val = val;
tail->next = NULL;
}
ListNode *head = dummy->next;
free(dummy);
// 输出原单链表数据
while (head) {
printf("--%d", head->val);
head = head->next;
}
printf("\n");
// 逆置单链表
head = reverseLinkedList(head);
// 输出逆置后的单链表数据
while (head) {
printf("--%d", head->val);
head = head->next;
}
printf("\n");
return 0;
}
```
其中,`reverseLinkedList` 函数实现了单链表的逆置操作,它接受一个链表头结点作为输入,返回逆置后的链表头结点。建立原单链表的部分使用了哑结点(dummy node)技巧,最后将其丢弃即可。注意,在动态内存分配时需要使用 `malloc` 函数分配空间,最后需要手动释放内存。
阅读全文