#include
#include
// 定义链表节点结构体
struct Node {
int data;
struct Node* next;
};
// 定义栈节点结构体
struct StackNode {
struct Node* data;
struct StackNode* next;
};
// 创建栈节点
struct StackNode* createStackNode(struct Node* data) {
struct StackNode* newStackNode = (struct StackNode*)malloc(sizeof(struct StackNode));
newStackNode->data = data;
newStackNode->next = NULL;
return newStackNode;
}
// 压栈
void push(struct StackNode top, struct Node* data) {
struct StackNode* newStackNode = createStackNode(data);
newStackNode->next = *top;
*top = newStackNode;
}
// 出栈
struct Node* pop(struct StackNode top) {
if (*top == NULL) {
return NULL;
}
struct StackNode* temp = *top;
*top = (*top)->next;
struct Node* popped = temp->data;
free(temp);
return popped;
}
// 使用栈逆序链表
struct Node* reverseListUsingStack(struct Node* head) {
struct StackNode* stack = NULL;
struct Node* current = head;
// 将链表节点压入栈中
while (current != NULL) {
push(&stack, current);
current = current->next;
}
// 弹出栈中的节点，重新连接成链表
head = pop(&stack);
current = head;
while (current != NULL) {
current->next = pop(&stack);
current = current->next;
}
return head;
}
// 创建新节点
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// 打印链表
void printList(struct Node* head) {
struct Node* current = head;
while (current != NULL) {
printf("%d -> ", current->data);
current = current->next;
}
printf("NULLn");
}
// 主函数
int main() {
struct Node* head = createNode(1);
head->next = createNode(2);
head->next->next = createNode(3);
head->next->next->next = createNode(4);
head->next->next->next->next = createNode(5);
printf("Original List: ");
printList(head);
head = reverseListUsingStack(head);
printf("Reversed List: ");
printList(head);
return 0;
}