單鏈表只能單向遍歷，無法直接從尾到頭訪問。實現逆序打印的經典思路是：遍歷原鏈表，將每個節點數據取出，用頭插法構建一個新鏈表。新鏈表的順序即為原鏈表的逆序。帶頭結點版本邏輯更清晰，無需處理空表特殊情況。
reverseHead。pMove = head->next。pInsert，複製數據，頭插到 reverseHead 後。reverseHead->next 指向的即為逆序鏈表。#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef int elemType;
typedef struct Node {
elemType element;
struct Node *next;
} Node;
// 初始化帶頭結點鏈表
void InitialList(Node **head) {
*head = (Node*)malloc(sizeof(Node));
(*head)->next = NULL;
}
// 尾插創建 (測試用)
void CreateList(Node *head) {
Node *pInsert, *pMove = head;
pInsert = (Node*)malloc(sizeof(Node));
pInsert->next = NULL;
scanf("%d", &pInsert->element);
while (pInsert->element > 0) {
pMove->next = pInsert;
pMove = pInsert;
pInsert = (Node*)malloc(sizeof(Node));
pInsert->next = NULL;
scanf("%d", &pInsert->element);
}
free(pInsert);
}
// 打印鏈表
void PrintList(Node *head) {
for (Node *p = head->next; p; p = p->next) printf("%d ", p->element);
printf("\n");
}
// 核心：逆序打印 (構建新鏈表法)
Node* ReversePrintList(Node *head) {
Node *reverseHead;
InitialList(&reverseHead); // 新鏈表頭結點
Node *pMove = head->next; // 遍歷原鏈表數據節點
Node *pInsert;
while (pMove) {
// 1. 分配新節點並複製數據
pInsert = (Node*)malloc(sizeof(Node));
pInsert->element = pMove->element;
pInsert->next = NULL;
// 2. 頭插法：插入 reverseHead 之後
pInsert->next = reverseHead->next;
reverseHead->next = pInsert;
pMove = pMove->next;
}
// 3. 打印逆序鏈表
printf("逆序輸出: ");
PrintList(reverseHead);
// 4. 釋放新鏈表內存 (良好習慣)
Node *tmp;
for (Node *p = reverseHead->next; p; ) {
tmp = p;
p = p->next;
free(tmp);
}
free(reverseHead);
return NULL; // 僅用於打印，不返回新鏈表
}
// 測試主函數
int main() {
Node *list;
InitialList(&list);
printf("請輸入數據 (正數構建，<=0 結束): ");
CreateList(list); // 例: 1 2 3 4 5 0
printf("原序列: ");
PrintList(list); // 1 2 3 4 5
ReversePrintList(list); // 逆序輸出: 5 4 3 2 1
// 清理原鏈表
Node *p;
for (p = list->next; p; ) {
Node *tmp = p; p = p->next; free(tmp);
}
free(list);
return 0;
}
請輸入數據 (正數構建，<=0 結束): 1 2 3 4 5 0 原序列: 1 2 3 4 5 逆序輸出: 5 4 3 2 1
| 方法 | 空間 | 優缺點 |
|---|---|---|
| 遞歸打印 | O(n) 棧 | 代碼極簡，但棧溢出風險，不適合長鏈表 |
| 棧輔助 | O(n) 堆 | 手動模擬遞歸，可控，但仍需 O(n) 空間 |
| 原地逆序 | O(1) | 修改指針方向，破壞原結構，需再逆序恢復 |
| 數組拷貝 | O(n) | 拷貝到數組逆序打印，緩存友好，實現最簡 |
void ReversePrintArray(Node *head) {
int len = 0;
for (Node *p = head->next; p; p = p->next) len++;
int *arr = malloc(len * sizeof(int));
int i = 0;
for (Node *p = head->next; p; p = p->next) arr[i++] = p->element;
for (i = len - 1; i >= 0; i--) printf("%d ", arr[i]);
printf("\n");
free(arr);
}
「頭插法構建新鏈表」是單鏈表逆序的標準教學解法，完美展示了頭插法「後進先出」的天然逆序特性。帶頭結點版本代碼最為優雅：無需判斷空表、無需特殊處理首節點。工程實際中，數組拷貝法因緩存局部性好、無內存碎片、代碼最短，往往是最佳選擇。掌握多種方案，根據場景 (嵌入式嚴格限制內存 vs 服務端追求簡潔) 靈活選型。
