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)，因为需要遍历整个链表一次。

相关问题

将一个带头结点的数据域依次为 a1，a2,...，an（n≥3）的单链表的所有结点逆置， 即第一个结点的数据域变为 an,...，最后一个结点的数据域为 a1。c语言编程实现以上功能要求。

可以使用三个指针分别指向当前遍历到的结点、该结点的前驱结点和该结点的后继结点，然后依次将当前结点的 next 指针指向前驱结点，然后将三个指针向后移动一个结点，循环直到遍历完整个链表。最后将原来的头结点指向新的尾结点即可。

下面是具体的代码实现：

void reverseList(Node* head) {
    if(head == NULL || head->next == NULL) {
        return;
    }
    Node *prev = NULL, *cur = head->next, *next = cur->next;
    while(next != NULL) {
        cur->next = prev;
        prev = cur;
        cur = next;
        next = next->next;
    }
    cur->next = prev;
    head->next = cur;
}

其中，Node 表示链表的结构体，包含数据域和指向下一个结点的指针 next。head 表示头结点，head->next 指向第一个数据结点。

将一个带头结点的数据域依次为 a1，a2,...，an（n≥3）的单链表的所有结点逆置，即第一个 结点的数据域变为 an,...，最后一个结点的数据域为 a1。c语言编程实现以上功能要求。

以下是实现此功能的C语言代码：

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int data;
    struct node *next;
} Node, *LinkedList;

LinkedList createList(int n) {
    LinkedList head = (LinkedList)malloc(sizeof(Node));
    head->next = NULL;
    LinkedList p = head;
    int i;
    for (i = 1; i <= n; i++) {
        LinkedList newNode = (LinkedList)malloc(sizeof(Node));
        newNode->data = i;
        newNode->next = NULL;
        p->next = newNode;
        p = p->next;
    }
    return head;
}

void printList(LinkedList head) {
    LinkedList p = head->next;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

void reverseList(LinkedList head) {
    if (head == NULL || head->next == NULL || head->next->next == NULL) {
        return;
    }
    LinkedList p = head->next;
    LinkedList q = p->next;
    p->next = NULL;
    while (q != NULL) {
        LinkedList temp = q->next;
        q->next = p;
        p = q;
        q = temp;
    }
    head->next = p;
}

int main() {
    LinkedList list = createList(5);
    printf("Original list: ");
    printList(list);

    reverseList(list);
    printf("Reversed list: ");
    printList(list);

    return 0;
}

这里我们首先定义了一个数据结构 `Node` 表示链表的结点，然后使用 `typedef` 定义了一个指向 `Node` 的指针类型 `LinkedList`，方便后面的代码书写。

接着，我们实现了 `createList()` 函数来创建一个单链表，该函数接受一个整数参数 n，表示链表的长度，返回创建好的链表头结点。

我们还实现了 `printList()` 函数来打印链表中的所有结点。

最后，我们实现了 `reverseList()` 函数来实现题目所要求的功能，即将链表中的所有结点逆序。该函数使用了双指针技巧，将链表中的每个结点的指针方向进行反转。

在 `main()` 函数中，我们先创建了一个长度为 5 的链表，然后分别打印原始链表和逆序后的链表。