视频字幕
链表反转是一种常见的链表操作，将链表节点的指向方向完全颠倒。例如，一个原始链表1指向2，2指向3，3指向4，4指向5，反转后变成5指向4，4指向3，3指向2，2指向1。这种操作在很多算法中都有应用，比如检测回文链表或者某些特定的链表处理场景。
迭代法是实现链表反转最常用的方法。我们需要使用三个指针：prev指向前一个节点，current指向当前处理的节点，next用于临时保存下一个节点。算法的核心是遍历链表，对每个节点执行四个步骤：首先，保存当前节点的下一个节点；然后，将当前节点的next指针指向前一个节点；接着，将prev指针移动到当前节点；最后，将current指针移动到下一个节点。循环结束后，prev指针将指向新的头节点，也就是原链表的最后一个节点。
递归法是实现链表反转的另一种方法，它利用函数调用栈来隐式地保存节点信息。递归法的基本思想是：先递归地反转子链表，然后再处理当前节点。具体步骤如下：首先，处理基本情况，如果链表为空或只有一个节点，则直接返回头节点；然后，递归地反转除了头节点外的子链表，得到新的头节点；接着，将子链表的尾节点（即原来的head->next）的next指针指向当前头节点；然后，将当前头节点的next指针置为nullptr；最后，返回新的头节点。递归法的代码更简洁，但会使用额外的栈空间，空间复杂度为O(n)。
让我们来看一个完整的C++链表反转示例，并分析两种方法的复杂度。在这个示例中，我们定义了链表节点结构，创建了一个包含5个节点的链表，然后调用反转函数并打印结果。从复杂度角度看，迭代法和递归法的时间复杂度都是O(n)，因为都需要遍历整个链表一次。但在空间复杂度上，迭代法只需要O(1)的额外空间，而递归法需要O(n)的栈空间。比较这两种方法，迭代法的优点是空间效率高，代码直观；缺点是需要维护多个指针。递归法的优点是代码简洁易懂；缺点是空间开销大，有栈溢出风险。在实际应用中，通常推荐使用迭代法，因为它更高效且不会有栈溢出的风险。
总结一下，链表反转是一种将链表节点指向方向完全颠倒的操作。我们学习了两种实现方法：迭代法使用三个指针遍历链表，空间复杂度为O(1)；递归法利用函数调用栈隐式保存节点信息，空间复杂度为O(n)。链表反转在许多算法问题中有广泛应用，例如检测回文链表、K个一组反转链表、重排链表、链表排序以及链表相交问题等。在实际编程中，链表反转是一个基础但非常重要的操作，掌握它对于解决更复杂的链表问题非常有帮助。