C语言实现链表逆序输出的多种方法详解109

链表是一种常用的数据结构，它在内存中以非连续的方式存储数据。链表的节点包含数据域和指针域，指针域指向下一个节点。逆序输出链表是指将链表中的节点按照相反的顺序输出。本文将详细介绍几种用C语言实现链表逆序输出的方法，并分析它们的优缺点。

一、递归方法

递归是一种简洁优雅的解决链表逆序输出的方法。其核心思想是：先递归地输出链表的后续节点，然后再输出当前节点的数据。```c
#include
#include
typedef struct Node {
int data;
struct Node *next;
} Node;
void reversePrintRecursive(Node *head) {
if (head == NULL) {
return;
}
reversePrintRecursive(head->next);
printf("%d ", head->data);
}
int main() {
Node *head = (Node *)malloc(sizeof(Node));
head->data = 1;
head->next = (Node *)malloc(sizeof(Node));
head->next->data = 2;
head->next->next = (Node *)malloc(sizeof(Node));
head->next->next->data = 3;
head->next->next->next = NULL;
printf("Reverse order: ");
reversePrintRecursive(head);
printf("");
//释放内存，避免内存泄漏
Node *temp = head;
while(temp != NULL){
Node *next = temp->next;
free(temp);
temp = next;
}
return 0;
}
```

该方法简洁易懂，但递归深度与链表长度成正比，对于非常长的链表，可能会导致栈溢出。因此，递归方法更适用于长度较短的链表。

二、迭代方法 (使用栈)

迭代方法避免了递归带来的栈溢出问题。我们可以使用一个栈来存储链表的节点，然后依次弹出栈顶元素并输出其数据。```c
#include
#include
#include //for INT_MAX
typedef struct Node {
int data;
struct Node *next;
} Node;
typedef struct Stack {
int top;
int capacity;
Node array;
}Stack;
Stack* createStack(int capacity){
Stack *stack = (Stack*)malloc(sizeof(Stack));
stack->capacity = capacity;
stack->top = -1;
stack->array = (Node)malloc(stack->capacity * sizeof(Node*));
return stack;
}
int isFull(Stack *stack){
return stack->top == stack->capacity -1;
}
void push(Stack *stack, Node *node){
if(isFull(stack)){
printf("Stack Overflow");
return;
}
stack->array[++stack->top] = node;
}
int isEmpty(Stack *stack){
return stack->top == -1;
}
Node* pop(Stack *stack){
if(isEmpty(stack)){
printf("Stack Underflow");
return NULL;
}
return stack->array[stack->top--];
}
void reversePrintIterativeStack(Node *head) {
Stack *stack = createStack(INT_MAX); //使用INT_MAX作为栈容量，避免容量限制
Node *current = head;
while (current != NULL) {
push(stack, current);
current = current->next;
}
while (!isEmpty(stack)) {
printf("%d ", pop(stack)->data);
}
free(stack->array);
free(stack);
}
int main() {
// ... (same as the recursive example) ...
printf("Reverse order (using stack): ");
reversePrintIterativeStack(head);
printf("");
//释放内存，避免内存泄漏
Node *temp = head;
while(temp != NULL){
Node *next = temp->next;
free(temp);
temp = next;
}
return 0;
}
```

这种方法的时间复杂度为O(n)，空间复杂度也为O(n)，适合处理各种长度的链表。

三、迭代方法 (原地逆序)

这种方法不需要额外的空间，通过改变链表的指针来实现原地逆序。它通过三个指针完成操作：prev、curr、next。```c
#include
#include
// ... (Node definition same as above) ...
void reversePrintIterativeInPlace(Node *head) {
Node *prev = NULL;
Node *curr = head;
Node *next = NULL;
while (curr != NULL) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
// 现在 prev 指向逆序链表的头节点
while (prev != NULL) {
printf("%d ", prev->data);
prev = prev->next;
}
}
int main() {
// ... (same as the recursive example) ...
printf("Reverse order (in-place): ");
reversePrintIterativeInPlace(head);
printf("");
//释放内存，避免内存泄漏
Node *temp = head;
while(temp != NULL){
Node *next = temp->next;
free(temp);
temp = next;
}
return 0;
}
```