【面试】4.单链表的反向
- 初始化：
p1指向原头节点，p2指向第二个节点；把原头节点的next设为NULL，为后面的翻转做准备。 - 循环体：先保存
p2的后继 (p1 = p2->next)；再把p2->next指向当前的head（已经翻转好的部分）；随后把head更新为p2，相当于把p2插入到已翻转链表的最前端；最后把p2移动到p1（即原链表的下一个节点）。 - 终止条件：当
p2为NULL时，说明所有节点都已经处理完毕。
2.3 复杂度分析
- 时间复杂度：
O(n)，遍历一次链表即可完成翻转。 - 空间复杂度：
O(1)，仅使用了常数个指针变量。
2.4 常见错误与调试技巧
| 错误情形 | 可能原因 | 解决办法 |
|---|---|---|
| 程序运行后链表出现环 | p2->next=*head 前未正确保存 p2->next | 确保在修改指针前先保存后继节点 (p1 = p2->next) |
| 逆序后头指针仍指向原头节点 | 未把 *head 更新为 p2 | 检查 *head = p2; 语句是否被遗漏 |
空链表（head == NULL）导致崩溃 | 未对空指针做保护 | 在函数入口加入 `if (!head |
3. 方法二：利用栈的先进后出特性
3.1 思路概述
栈（std::stack）天然具备 后进先出（LIFO）的特性。将链表的所有节点依次压入栈中后，弹出时的顺序正好是原链表的逆序。通过遍历栈并重新链接节点，即可得到翻转后的链表。