给出c语言代码,写算法,借助于栈将一个单链表逆置。
时间: 2023-06-14 11:04:11 浏览: 57
以下是使用栈将单链表逆置的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
void push(struct Node** topRef, int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Stack overflow!\n");
exit(1);
}
newNode->data = data;
newNode->next = *topRef;
*topRef = newNode;
}
int pop(struct Node** topRef) {
if (*topRef == NULL) {
printf("Stack underflow!\n");
exit(1);
}
struct Node* temp = *topRef;
int data = temp->data;
*topRef = temp->next;
free(temp);
return data;
}
void reverseLinkedList(struct Node** headRef) {
struct Node* current = *headRef;
struct Node* stack = NULL;
while (current != NULL) {
push(&stack, current->data);
current = current->next;
}
current = *headRef;
while (current != NULL) {
current->data = pop(&stack);
current = current->next;
}
}
void printLinkedList(struct Node* node) {
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
printf("\n");
}
int main() {
struct Node* head = NULL;
// Create a linked list: 1 -> 2 -> 3 -> 4 -> 5
push(&head, 5);
push(&head, 4);
push(&head, 3);
push(&head, 2);
push(&head, 1);
printf("Original linked list: ");
printLinkedList(head);
reverseLinkedList(&head);
printf("Reversed linked list: ");
printLinkedList(head);
return 0;
}
```
这个算法的基本思路是,首先将原始单链表中的元素依次压入栈中,然后再依次从栈中弹出元素,将其赋值给原始单链表中的每个节点。