1.设计一个算法，将带头结点的数据域依次为a1,a2…an的单链表的所有结点逆置，即第1个结点的数据域变为an,第2个结点的数据域变为an-1…最后一个结点的数据域为a1 。要求算法的时间复杂度为O（n）;.c语言

可以使用三个指针分别指向当前处理的结点、它的前驱结点和后继结点。具体步骤如下：

void reverseList(Node* head) {
    if (head == NULL || head->next == NULL) {
        return;
    }
    Node *pre = head, *cur = head->next, *next = cur->next;
    pre->next = NULL; // 将头节点作为新链表的尾结点
    while (next != NULL) {
        cur->next = pre; // 反转当前结点
        pre = cur;       // 更新前驱结点
        cur = next;      // 更新当前结点
        next = next->next; // 更新后继结点
    }
    cur->next = pre;     // 反转最后一个结点
    head->next = cur;    // 将反转后的链表接到头节点后面
}

时间复杂度为O(n)，空间复杂度为O(1)。