题目：
给单链表的头节点，反转链表，并返回反转后的链表。
方法一：迭代
在遍历链表时，将当前节点的next指针改为指向前一个节点。由于节点没有引用其前一个节点，因此要先存储前一个节点，在更改引用之前，还要存储后一个节点，最后返回新的头引用。
链表注意：上一个，现在，下一个的关系
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):def reverseList(self, head):""":type head: Optional[ListNode]:rtype: Optional[ListNode]"""prev=None #用来追踪上一个节点的指针，初始为空curr=head #当前处理的节点，初始化为链表的头节点while curr is not None:next_node=curr.next #当前节点指向的下一个节点curr.next=prev #反转当前节点的指向，让当前节点指向前一个节点prev=curr #将前一指针移动到当前节点curr,以便下一个节点反转时，当前节点成为下一个节点的前驱节点curr=next_node #指针后移，继续遍历return prev时间复杂度：O(N)
空间复杂度：O(1)
方法二：递归
假设链表为：n1→…→nk−1→nk→nk+1→…→nm→∅
若从节点nk+1到nm已经被反转，而我们处于nk,n1→…→nk−1→nk→nk+1←…←nm
希望nk.next.next=nk
需要注意的是 n1 的下一个节点必须指向 ∅。如果忽略了这一点，链表中可能会产生环。
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):def reverseList(self, head):""":type head: Optional[ListNode]:rtype: Optional[ListNode]"""if head is None or head.next is None: #链表为空或者链表只有一个节点，返回当前节点return headnewhead=self.reverseList(head.next) #对链表的下一个节点递归调用，直到链表末尾head.next.next=head #反转指针，当前节点head设为下一个节点head.next 的下一个节点head.next=None #将当前节点 head 的 next 指针设为 None，避免形成环return newhead时间复杂度：O(N)
空间复杂度：O(N)