957: 逆置单链表

### 单链表逆置的实现方法 单链表逆置是一种常见的数据结构操作，其核心在于改变链表中节点之间的指向关系。以下是几种常用的单链表逆置方法及其具体实现。 #### 方法一：头插法 头插法的核心思想是通过不断将当前节点插入到新链表头部的方式构建逆序链表。这种方法不需要额外的空间开销，仅需调整指针即可完成链表的逆置[^2]。 下面是基于头插法的代码实现： ```c++ struct ListNode { int val; ListNode* next; }; ListNode* reverseList(ListNode* head) { ListNode* newHead = nullptr; // 新链表的头结点初始化为空 while (head != nullptr) { ListNode* temp = head->next; // 保存下一个节点 head->next = newHead; // 当前节点指向前一个节点（即新的头） newHead = head; // 更新新链表的头结点 head = temp; // 移动到原始链表的下一个节点 } return newHead; // 返回逆置后的链表头 } ``` 此方法的时间复杂度为 \(O(n)\)，其中 \(n\) 是链表长度，因为每个节点都需要被访问一次并重新连接[^3]。 --- #### 方法二：迭代法 迭代法本质上与头插法相似，但它更强调逐步处理每一个节点的过程。同样地，它也只需要常量级别的额外空间来存储临时变量。 下面是一个具体的实现方式： ```cpp ListNode* reverseListIteratively(ListNode* head) { ListNode* prev = nullptr; // 前驱节点初始为空 ListNode* curr = head; // 当前节点从头开始 while (curr != nullptr) { // 遍历整个链表 ListNode* nextTemp = curr->next; // 保存下一节点 curr->next = prev; // 反转当前节点的指针方向 prev = curr; // 将当前节点设为前驱节点 curr = nextTemp; // 继续处理下一节点 } return prev; // 最终返回prev作为新的头结点 } ``` 上述代码展示了如何利用 `prev` 和 `curr` 来逐个反转链表中的节点。 --- #### 方法三：递归法 递归法的思想是从链表尾部开始逐渐建立逆向链接。虽然递归方法更加简洁优雅，但由于函数调用栈的存在，可能会带来较大的内存消耗，尤其对于非常长的链表而言可能引发堆栈溢出问题。 递归版本如下所示： ```cpp ListNode* reverseListRecursively(ListNode* head) { if (!head || !head->next) return head; // 如果到达末尾或者只有一个节点，则直接返回 ListNode* reversedTail = reverseListRecursively(head->next); // 对后续部分进行递归翻转 head->next->next = head; // 调整当前节点与其后继的关系 head->next = nullptr; // 断开原有指向以防成环 return reversedTail; // 返回最终的新头结点 } ``` 递归方法的时间复杂度同样是 \(O(n)\)，但在实际应用中需要注意潜在的性能瓶颈。 --- #### 方法四：辅助栈法 如果允许使用额外的数据结构，可以通过栈这种先进后出的数据特性轻松解决链表逆置问题。尽管这种方式增加了空间成本，但对于某些特定场景可能是更为直观的选择。 伪代码描述如下： 1. 创建一个空栈； 2. 遍历原链表并将各节点压入栈中； 3. 出栈的同时重构链表顺序。 注意，这种方法并不推荐用于追求高效性的场合，因为它不仅需要线性时间复杂度的操作，还需要额外的存储资源[^1]。 --- ### 总结 以上介绍了四种不同的单链表逆置技术——头插法、迭代法、递归法以及借助栈的方法。每种都有各自的优劣之处，在实际开发过程中可以根据需求灵活选用合适的方案。