C语言链表逆序输出的多种方法详解及性能分析264

链表是一种常用的数据结构，其特点在于节点的存储地址不连续，通过指针连接各个节点。在链表应用中，经常需要对链表进行逆序输出。本文将详细介绍几种C语言实现链表逆序输出的方法，并对它们的性能进行分析，帮助读者选择最合适的算法。

一、递归方法

递归是一种简洁优雅的解决链表逆序输出的方法。其核心思想是先递归地输出链表的尾部节点，再输出当前节点。当到达链表尾部时，递归结束，开始回溯输出。
#include <stdio.h>
#include <stdlib.h>
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("Reversed linked list: ");
reversePrintRecursive(head);
printf("");
// 释放内存，避免内存泄漏
Node *current = head;
while (current != NULL) {
Node *next = current->next;
free(current);
current = next;
}
return 0;
}

这种方法代码简洁，易于理解，但存在递归深度的问题。对于非常长的链表，可能会导致栈溢出。因此，对于大型链表，递归方法并不推荐。

二、迭代方法

迭代方法避免了递归的栈溢出问题。它使用三个指针：prev, current, next 来迭代遍历链表，并逐步反转链表的指针指向。
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
void reversePrintIterative(Node *head) {
Node *prev = NULL;
Node *current = head;
Node *next = NULL;
while (current != NULL) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
// 此时 prev 指向反转后的链表头
while (prev != NULL) {
printf("%d ", prev->data);
prev = prev->next;
}
printf("");
}
int main() {
// ... (same as recursive example) ...
printf("Reversed linked list (iterative): ");
reversePrintIterative(head);
// ... (memory release as before) ...
return 0;
}

迭代方法的时间复杂度为O(n)，空间复杂度为O(1)，效率更高，也更稳定，适用于各种规模的链表。

三、使用栈

利用栈的后进先出特性，可以先将链表的节点依次压入栈中，然后依次弹出并输出，实现逆序输出。
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
#include <stack> //需要包含stack头文件
void reversePrintStack(Node *head) {
std::stack<int> s;
Node *current = head;
while (current != NULL) {
(current->data);
current = current->next;
}
while (!()) {
printf("%d ", ());
();
}
printf("");
}
int main() {
// ... (same as recursive example) ...
printf("Reversed linked list (stack): ");
reversePrintStack(head);
// ... (memory release as before) ...
return 0;
}