一、题目描述

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

注意：头指针和头节点的区别

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

• 链表中节点的数目范围是 [0, 5000]
• -5000 <= Node.val <= 5000

方法一 迭代法

核心思想

逐个反转节点的next指针

我们定义三个指针：

curr:表示当前正在处理的节点（初始为head）

pre:表示前面已经反转过的节点的第一个节点(初始为None)

next_term:保存下一个节点，防止断链

操作步骤：

1、保存next_term=curr.next 防止断链

2、反转节点的指针，是指针指向前一个结点curr.next=pre

3、向前推进 pre=curr,curr=next_term

4、循环直到 curr为None

5、返回pre(此时为新链表头)

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseList(head):
    prev = None
    curr = head
    while curr:
        next_node = curr.next  # 1️⃣ 暂存下一个节点
        curr.next = prev       # 2️⃣ 反转指针
        prev = curr            # 3️⃣ 向前移动 prev
        curr = next_node       # 4️⃣ 向前移动 curr
    return prev

方法二 递归法

核心思想：

从后往前反转链表。当递归到最后一个节点时，将其作为新头返回，然后逐层回溯修改指针。

代码：

def reverseList(head):
    # 递归终止条件：空链表或单节点
    if not head or not head.next:
        return head
    new_head = reverseList(head.next)  # 递归反转剩余链表
    head.next.next = head  # 当前节点的下一个节点指向自己
    head.next = None       # 断开当前节点的 next
    return new_head