根据用户输入的数据逆置当前的单链表，即将线性表(a0, a1, …, an-1)变成(an-1, an-2, …, a0)，要求时间复杂度是0(N)

在C++中，如果允许常数额外空间并且时间复杂度为O(n)，那么可以使用迭代的方式，避免创建额外的链表，直接在原地修改链表。这种技术叫做“双指针法”，因为我们需要两个指针同时移动。

假设我们有一个单链表，其结构类似于这样的 `struct ListNode`：

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

逆置链表的过程可以这样描述：

ListNode* reverseList(ListNode* head) {
    if (!head || !head->next) {
        return head; // 如果链表为空或只有一个元素，不需要反转
    }
    
    ListNode *prev = NULL; // 初始化一个空指针，用于存放上一个节点
    ListNode *curr = head; // 初始化当前指针，开始于链表的第一个元素
    
    // 双指针法
    while (curr != NULL) {
        ListNode *nextTemp = curr->next; // 保存当前节点的下一个节点
        curr->next = prev; // 将当前节点的next指向前一个节点
        prev = curr; // 更新前驱为当前节点
        curr = nextTemp; // 移动当前指针到下一个节点
    }
    
    // 转换原头节点为新尾节点
    head = prev;
    return head;
}

此算法在每次循环中都将链表的一部分反转过来，直到整个链表都被处理完。