给定一个带头结点的单链表，编写算法将其原地逆置。所谓“原地”是指空间复杂度为O(1)。 测试用例 输入：5 1 3 5 7 9 输出:9 7 5 3 1

思路：

1. 定义三个指针pre、p、next，分别指向当前节点的前一个节点、当前节点、当前节点的后一个节点。

2. 遍历链表，将当前节点的next指向pre，然后依次向后移动pre、p、next指针。

3. 最后将头结点的next指向pre，完成链表的逆置。

代码实现：

def reverseList(head):
    if head is None or head.next is None:
        return head
    pre = None
    p = head.next
    while p is not None:
        next = p.next
        p.next = pre
        pre = p
        p = next
    head.next = pre
    return head

时间复杂度：O(n)

空间复杂度：O(1)