2、请试编写算法将带头节点的单链表就地逆置，所谓“就地”是辅助空间复杂度为O(1)。

在Python中，我们可以使用迭代的方式实现单链表的就地逆置，这种方法不需要额外的空间，时间复杂度是O(n)，其中n是链表的长度。以下是算法的步骤：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseList(head):
    prev = None
    curr = head
    while curr is not None:
        # 保存当前节点的下一个节点
        next_temp = curr.next
        # 将当前节点指向prev
        curr.next = prev
        # 移动prev和curr指针
        prev = curr
        curr = next_temp
    return prev  # 返回新的头节点，原头现在是最后一个节点

# 示例
# 初始化链表
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)

# 逆置链表
new_head = reverseList(head)
while new_head is not None:
    print(new_head.val, end=" -> ")
    new_head = new_head.next
print("None")  # 输出：3 -> 2 -> 1 -> None