力扣(LeetCode)之链表反转

首先我们回忆一下什么是链表？
其实链表很简单，链表就是由许多个链表节点构成，每一个链表节点里面包含两个部分:value, next。value指的是当前的数据的值，next指的是下一个链表节点的地址，这样一个连着一个就被称之为：链表。

题目：

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

[图片上传失败...(image-8befea-1693465332616)]

示例：

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

方法1：使用迭代法

我们可以判断这个题目的操作肯定是一个重复的循环结构，我们需要一个cur变量用于指向当前的链表节点，并且需要一个next变量用于保存cur.next，。链表反转，我们需要将链表的next指向上一个链表节点，我们使用一个prev变量保存，但是需要注意的是此时的prev变量是为了给下一个节点使用的，所以此时的prev保存的是当前cur修改了next之后的节点。最后将cur变量移动到下一个节点，cur = next。

# 迭代方法
def fun1(head_node):
    cur = head_node
    prev_ = None
    next_ = 0
    while cur:
        next_ = cur.next # 保存下一个节点
        cur.next = prev_ # 修改当前的node的next
        prev_ = cur # 保存修改后的cur
        cur = next_ # 移动到下一个节点
    return prev_

方法2：使用递归法

使用递归法的时候，首先我们需要进入到链表的最后一层。到达最后一层的时候我们将会返回最后一个节点，使用node变量接收。此时head_node指向倒数第二个节点，node始终是最后一个节点，我们将head_node.next.next修改为head_node。这样我们就能够实现链表反转。

# 递归方法
def fun2(head_node): # [5 -> 4 -> 3 -> 2 -> 1]
    if head_node == None or head_node.next == None:
        return head_node  
    node = fun2(head_node.next) # 返回最后一个节点，head_node.val = 2
    head_node.next.next = head_node # [5 -> 4 -> 3 -> 2 <- 1]
    head_node.next = None # [None <- 2 <- 1]
    return node # [None <- 2 <- 1]