难度: 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进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
注意：本题与主站 206 题相同： https://leetcode-cn.com/problems/reverse-linked-list/
运行时间: 18 ms
内存: 16.8 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: ListNode) -> ListNode:
prev = None
cur = head
while cur:
tmp = cur.next
cur.next = prev
prev = cur
cur = tmp
return prev
该题解采用了迭代方式反转单链表。初始化一个指针prev为None，然后用cur指向链表的头节点head。在迭代过程中，将当前节点cur的next指针指向prev，实现反转。随后，prev移动到cur的位置，cur则移动到原来的next位置。这个过程一直持续到cur为None，即遍历完整个链表。最后返回prev，此时prev指向原链表的末尾节点，即反转后的头节点。
时间复杂度: 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: ListNode) -> ListNode:
prev = None # 初始化前一个节点为None
cur = head # 当前节点从头节点开始
while cur: # 遍历链表
tmp = cur.next # 保存当前节点的下一个节点
cur.next = prev # 反转当前节点的指向
prev = cur # 移动prev到当前节点
cur = tmp # 继续向下一个节点移动
return prev # 返回反转后的头节点
在反转链表的过程中，我们需要改变当前节点cur的next指针，指向前一个节点prev。如果不使用额外的变量tmp来保存cur.next的值，一旦cur.next被修改指向prev，原来cur.next的信息就会丢失，这会导致我们无法继续访问链表的下一个节点。因此，使用tmp变量来保存cur.next是必须的，以便在修改cur.next后，可以通过tmp移动到链表的下一个节点。
这种迭代反转链表的算法可以直接应用于链表长度为1或者链表为空的情形，无需特殊处理。当链表长度为1时，cur指向该唯一的节点，反转操作后cur.next将指向None（即prev的初始值），整个链表反转后仍然是该单个节点，符合预期。如果链表为空，即head为None，while循环不会执行，直接返回prev（None），这也符合链表为空时的预期结果。
在每次迭代过程中，当前节点cur的next都被改指向前一个节点prev，这样就逐步构建了反向的链表链接。随着迭代的进行，prev逐渐移动，从None到原链表的第一个节点，依次向后移动。当cur遍历完整个链表，即cur变为None时，prev将位于原链表的最后一个节点，这时所有节点的指向都已经完全反转。因此，此时的prev实际上已经成为了新链表的头节点。