难度: Easy
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
进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
运行时间: 36 ms
内存: 16 MB
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
cur = head
pre = None
while cur:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
return pre
这个题解使用了迭代的方式来反转链表。具体做法是：用两个指针cur和pre分别指向当前节点和前一个节点。每次迭代时，先用tmp指针保存cur的下一个节点，然后将cur的next指针指向pre，完成当前节点的反转。接着把pre和cur分别往后移动一个节点，继续下一轮迭代，直到cur变为None时结束。最后pre指针就指向了新的链表头。
时间复杂度: O(n)
空间复杂度: O(1)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
cur = head # 当前节点指针
pre = None # 前一个节点指针
while cur: # 遍历链表
tmp = cur.next # 临时保存当前节点的下一个节点
cur.next = pre # 反转当前节点的next指针
pre = cur # 更新pre指针到当前节点
cur = tmp # 更新当前节点到下一个节点
return pre # 返回新的链表头节点
如果链表为空（即head为None），则cur也将为None。由于循环的条件是'while cur'，循环不会开始执行，因此函数直接返回pre，此时pre也是None，这与输入的空链表相符。如果链表只有一个节点，迭代会开始，但只进行一次。在这次迭代中，tmp保存cur.next（即None），cur.next被设置为pre（也是None）。然后pre更新为cur（指向这唯一的节点），cur更新为tmp（None）。循环结束，此时pre指向反转后的链表头，即原链表的唯一节点。因此，算法能正确处理长度为0或1的链表。
迭代方法相较于递归方法的优势主要在于空间复杂度。迭代方法只用到了几个节点指针，空间复杂度为O(1)，而递归方法由于递归调用会不断增加调用栈，其空间复杂度为O(n)，n是链表的长度。此外，迭代方法通常对初学者来说逻辑更直观，易于调试和理解。递归方法虽然代码更简洁，但在处理较长的链表时可能会导致栈溢出。
在迭代反转链表的过程中，'pre'指针用于保存已经反转部分的最后一个节点，'cur'指针指向当前正在处理的节点，'tmp'是一个临时指针，用来保存下一个待处理的节点（即cur.next），防止链表断裂。迭代的每一步中，首先用tmp保存cur.next，然后将cur.next指向pre（实现反转），接着将pre移动到cur，最后将cur移动到tmp。这样，pre逐渐成为新链表的头部，cur遍历整个原链表。
在迭代过程中，每次循环都会将当前节点cur的next指针指向前一个节点pre，从而实现节点的反转。对于最后一个节点，由于在迭代开始时已经将cur设置为头节点，因此最后一个节点也会在迭代中被处理到。当处理到最后一个节点时，cur.next将被设置为pre，完成最后一个节点的反转，然后pre更新为最后一个节点。此时cur更新为None，循环结束。函数最后返回pre，此时pre指向新的链表头，即原链表的最后一个节点。这样确保了链表中的所有节点都被正确反转。