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

可以使用头插法来实现单链表的逆置。具体的步骤如下：

1. 定义一个新的头结点newHead，并让它的next指针指向原链表的头结点head。
2. 定义一个指针p，初始时指向原链表的第一个结点head->next。
3. 定义一个指针q，初始时指向p->next。
4. 将p的next指针指向newHead的next指针所指向的结点，即p->next = newHead->next。
5. 将newHead的next指针指向p，即newHead->next = p。
6. 将p指针后移，指向q所指向的结点，即p = q。
7. 如果p不为空，则重复步骤3~6，否则逆置结束。

代码实现如下：

void reverseList(ListNode* head) {
    ListNode* newHead = (ListNode*)malloc(sizeof(ListNode));
    newHead->next = head;
    ListNode* p = head->next;
    while (p != NULL) {
        ListNode* q = p->next;
        p->next = newHead->next;
        newHead->next = p;
        p = q;
    }
    head->next = newHead->next;
    free(newHead);
}

时间复杂度为O(n)，因为需要遍历整个链表一次。