一、题目（含示例）

题目描述：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：输入：head = [1,2,3,4,5]输出：[5,4,3,2,1]解释：原链表为 1->2->3->4->5，反转后为 5->4->3->2->1。

示例 2：输入：head = [1,2]输出：[2,1]解释：原链表为 1->2，反转后为 2->1。

示例 3：输入：head = []输出：[]解释：空链表反转后仍为空链表。

二、解题关键（难点和核心逻辑）难点：

• 链表指针操作易出错，需避免出现环或断裂（如反转后尾节点未指向 None 导致环）；
• 递归法需理解 “从后往前” 的反转逻辑，避免递归栈溢出；
• 栈方法需正确处理节点入栈、出栈及重新链接的顺序。

核心逻辑：

1. 递归法：利用递归栈 “从后往前” 反转指针。先递归反转当前节点的后续子链表，再将当前节点与下一个节点的指针反转（下一个节点指向当前节点，当前节点指向 None），最终返回原链表的尾节点（反转后的头节点）。
2. 双指针法：通过前驱指针（pre）和当前指针（cur）迭代反转。每次保存当前节点的下一个节点，再将当前节点指向前驱节点，随后移动两指针，直至遍历完链表，前驱指针即为反转后的头节点。
3. 栈方法：利用栈 “后进先出” 特性。先将所有节点入栈，再依次出栈并重新链接（每个出栈节点链接到上一个节点之后），最后处理尾节点指向 None 避免环。

三、解题基础知识点

1. 链表结构：由节点组成，每个节点包含值（val）和指向下一节点的指针（next），尾节点的 next 为 None。
2. 递归原理：函数自身调用需明确终止条件（如空链表或单节点），并通过递归栈传递中间结果（如反转后的子链表头节点）。
3. 双指针技巧：通过两个指针分工（如遍历与记录位置），在一次遍历中完成操作，降低空间复杂度。
4. 栈的特性：后进先出（LIFO），适合需要 “逆序处理” 的场景（如反转链表时从尾节点开始重构）。

四、完整代码实现（代码中所有运用的函数进行详细解释）

from typing import Optional

# 链表节点定义（三种方法共用）
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val  # 节点值
        self.next = next  # 指向下一节点的指针

# 辅助函数：列表转链表（便于构造测试用例）
def list_to_linkedlist(arr: list) -> Optional[ListNode]:
    if not arr:  # 空列表返回空链表
        return None
    head = ListNode(arr[0])  # 头节点为列表第一个元素
    current = head  # 当前节点指针，初始指向头节点
    for val in arr[1:]:  # 依次创建后续节点并链接
        current.next = ListNode(val)
        current = current.next  # 移动当前指针到新节点
    return head

# 辅助函数：链表转列表（便于查看结果）
def linkedlist_to_list(head: Optional[ListNode]) -> list:
    result = []
    current = head  # 从头部开始遍历
    while current:  # 遍历至尾节点（current为None时停止）
        result.append(current.val)  # 收集节点值
        current = current.next  # 移动到下一节点
    return result

# 解法1：递归法
class Solution1:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 终止条件：空链表或单节点无需反转
        if not head or not head.next:
            return head
        
        # 递归反转后续子链表，返回反转后的头节点（原尾节点）
        new_head = self.reverseList(head.next)
        
        # 反转当前节点与下一节点的指针
        head.next.next = head  # 下一节点指向当前节点
        head.next = None  # 当前节点指向None（避免环）
        
        return new_head  # 返回反转后的头节点

# 解法2：双指针法
class Solution2:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        pre = None  # 前驱指针，初始为None（原头节点的前驱）
        cur = head  # 当前指针，初始指向头节点
        
        while cur:  # 遍历所有节点
            next_node = cur.next  # 保存当前节点的下一节点（避免丢失）
            cur.next = pre  # 当前节点指向前驱节点（反转指针）
            pre = cur  # 前驱指针后移到当前节点
            cur = next_node  # 当前指针后移到保存的下一节点
        
        return pre  # 循环结束后，pre为反转后的头节点

# 解法3：栈方法
class Solution3:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        stack = []
        current = head
        
        # 所有节点入栈
        while current:
            stack.append(current)  # 入栈节点本身
            current = current.next
        
        if not stack:  # 空链表直接返回None
            return None
        
        # 虚拟头节点辅助重构链表
        dummy = ListNode(0)
        prev = dummy  # 跟踪当前链表尾部
        
        # 出栈并链接节点（逆序）
        while stack:
            node = stack.pop()  # 栈顶为原尾节点，依次弹出
            prev.next = node  # 链接到当前链表尾部
            prev = node  # 移动尾部指针
        
        prev.next = None  # 尾节点指向None，避免环
        
        return dummy.next  # 返回有效头节点

# 测试代码（三种方法共用）
if __name__ == "__main__":
    # 测试用例1：[1,2,3,4,5]
    test_arr1 = [1,2,3,4,5]
    head1 = list_to_linkedlist(test_arr1)
    
    # 递归法测试
    sol1 = Solution1()
    reversed1 = sol1.reverseList(head1)
    print(f"递归法 输入{test_arr1}，输出{linkedlist_to_list(reversed1)}（预期[5,4,3,2,1]）")
    
    # 双指针法测试（需重新构造链表，避免原链表被修改影响结果）
    head2 = list_to_linkedlist(test_arr1)
    sol2 = Solution2()
    reversed2 = sol2.reverseList(head2)
    print(f"双指针法 输入{test_arr1}，输出{linkedlist_to_list(reversed2)}（预期[5,4,3,2,1]）")
    
    # 栈方法测试
    head3 = list_to_linkedlist(test_arr1)
    sol3 = Solution3()
    reversed3 = sol3.reverseList(head3)
    print(f"栈方法 输入{test_arr1}，输出{linkedlist_to_list(reversed3)}（预期[5,4,3,2,1]）")

代码解释：

• 辅助函数 list_to_linkedlist：将列表转为链表，便于用 [1,2,3] 直观构造输入；
• 辅助函数 linkedlist_to_list：将链表转为列表，便于查看反转后的结果；
• 递归法（Solution1）：通过递归先处理后续节点，再反转当前节点与下一节点的指针，核心是 head.next.next = head 和 head.next = None；还需要理解的精髓： new_head = self.reverseList(head.next)（new_head 的头这个节点的地址被获取并固定）
• 双指针法（Solution2）：通过 pre 和 cur 迭代反转，每次保存 next_node 避免链表断裂，最终 pre 为反转后的头节点；
• 栈方法（Solution3）：节点入栈后逆序出栈，通过 dummy 节点辅助链接，最后将尾节点 next 设为 None 避免环。

五、进阶知识

1. 复杂度对比：

   • 递归法：时间复杂度 O (n)（遍历所有节点），空间复杂度 O (n)（递归栈深度为链表长度）；
   • 双指针法：时间复杂度 O (n)，空间复杂度 O (1)（仅用两个指针），是最优解法；
   • 栈方法：时间复杂度 O (n)（入栈和出栈各遍历一次），空间复杂度 O (n)（栈存储所有节点）。

2. 适用场景：

   • 双指针法：优先选择，适合追求空间效率的场景；
   • 递归法：逻辑清晰但空间开销大，适合理解递归思想；
   • 栈方法：思路直观，适合对栈操作熟悉的场景。

3. 边界情况处理：

   • 空链表（head = None）：三种方法均返回 None；
   • 单节点链表（如 [1]）：无需反转，直接返回原节点；
   • 避免环的关键：反转后原头节点需指向 None（递归法的 head.next = None、栈方法的 prev.next = None）。