题解 | #反转链表#

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @return ListNode类
class Solution:
    def ReverseList(self, head: ListNode) -> ListNode:
        prev = None
        currt = head

        while curr is not None:
            next_node = currt.next  # 保存当前节点的下一个节点
            currt.next = prev       # 反转当前节点，指向前一个节点
            prev = currt            # 更新prev指针
            currt = next_node       # 继续下一次迭代

        return prev  # 返回反转后的链表头部

算法的思路是使用迭代的方式，从链表的头部开始遍历，通过不断改变指针的指向来逐步反转整个链表。

具体步骤如下：

1. 初始化三个指针：`prev`、`currt`和`next_node`。

- `prev`：初始为`None`，用于保存当前节点的前一个节点，因为在反转时我们需要将当前节点的`next`指向它的前一个节点。

- `currt`：初始为链表的头结点`head`，用于遍历整个链表。

- `next_node`：用于保存当前节点的下一个节点的指针，因为在反转当前节点之前，我们需要保存它的下一个节点，否则在反转后会丢失后续节点的信息。

2. 开始迭代：

- 在迭代过程中，我们不断更新`currt`节点的`next`指向`prev`节点，实现反转操作。

- 在执行反转之前，需要保存`currt`节点的下一个节点为`next_node`，否则反转后会丢失后续节点的信息。

- 然后将`prev`指向`currt`，`currt`指向`next_node`，继续下一次迭代。

3. 迭代终止：

- 当`currt`指针指向`None`时，表示已经遍历完整个链表，此时反转操作完成。

4. 返回新链表头：

- 由于在迭代过程中，`prev`指针移动到了最后一个节点，也就是反转后的链表头部。

- 我们直接返回`prev`作为新的链表头部即可。

这样，通过迭代地将当前节点的`next`指向前一个节点，逐步改变指针的指向，就完成了链表的反转操作。该算法的时间复杂度为O(n)，其中n是链表的长度，因为我们需要遍历整个链表。空间复杂度为O(1)，因为我们只使用了常数级别的额外空间用于存储三个指针。

上面说法太官方了，我用我通俗的想法说一下

首先，反转链表，可以理解为后面的节点转变为前面的，所以我们设定一个指针prev(previous)，用来表示当前节点的前面的节点，用currt(currtent),表示当前的节点，我们需要使用这个指针来遍历整个链表。

现在我们分析，一个链表走完的标志是节点值变成了None，所以我们prev最开始是currt（也就是head链表）的最后，因为head反转后就是最后一项，那么最后一项的后面肯定为None，所以我们初始或prev = None。

在循环过程中出现currt变为None，则代表链表循环已经完成。