C++ 鏈表逆序：遞歸法與頭插法完整實現對比

兩種經典算法

1. 遞歸法

思路：遞歸到達尾節點，回溯時反轉指針。
reverse(node) { if (!node||!node->next) { head=node; return; } reverse(node->next); node->next->next=node; node->next=nullptr; }

2. 頭插法（迭代）

思路：建立新頭節點，遍歷原鏈表，將每個節點摘下插入新頭之後。
while (cur) { nxt=cur->next; cur->next=newHead->next; newHead->next=cur; cur=nxt; }

完整可運行代碼（含測試）

方法時間空間備註
遞歸O(n)O(n) 棧代碼簡潔，棧溢出風險
頭插法O(n)O(1)生產環境首選


常見錯誤

忘記斷開原尾節點的 next（遞歸中 p->next=nullptr 必不可少）。
頭插法未保存 nxt 導致鏈表斷裂。
空鏈表、單節點邊界未處理。