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，第 2 个结点的数据域变为 an-1，...，尾 结点的数据域为 a1。c语言

在C语言中，我们可以设计一个递归算法来反转单链表。这里是一个基本的实现思路：

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

// 定义链表节点结构体
typedef struct ListNode {
    int val;   // 数据域
    struct ListNode *next; // 指向下一个节点的指针
} ListNode;

// 创建新节点
ListNode* createNode(int val) {
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    newNode->val = val;
    newNode->next = NULL;
    return newNode;
}

// 反转链表的辅助函数（递归）
ListNode* reverseListRec(ListNode* head) {
    if (head == NULL || head->next == NULL) {
        // 链表只有一个元素或为空，直接返回
        return head;
    }
    
    // 递归处理剩余部分
    ListNode* rest = reverseListRec(head->next);
    
    // 将当前节点的next指向头节点，完成反转
    head->next->next = head;
    head->next = NULL;
    
    return rest;
}

// 主函数测试
void printList(ListNode* head) {
    ListNode* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->val);
        temp = temp->next;
    }
    printf("NULL\n");
}

int main() {
    // 初始化一个示例链表
    ListNode* head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);
    head->next->next->next = createNode(4);
    
    printf("Original list: ");
    printList(head);
    
    head = reverseListRec(head); // 反转链表
    printf("\nReversed list: ");
    printList(head);
    
    return 0;
}

使用C++，设计一个算法,将一个带头结点的数据域依次为 a1、a2、…、an(n≥3)的单链表的 所有结点逆置,即第1个结点的数据域变为an,第2个结点的数据域变为an-1…,尾结点 的数据域变为 a1。

在C++中，我们可以使用迭代的方式来实现单链表的逆置。以下是一个简单的算法：

首先，我们需要定义链表节点结构体 `Node`：

struct Node {
    int data;
    Node* next;
};

然后创建两个指针，一个指向当前节点 (`current`)，另一个指向前一个节点 (`prev`)，初始时 `prev` 指向 `nullptr`，`current` 指向头节点 (`head`):

Node* prev = nullptr;
Node* current = head;

接下来，我们遍历整个链表：

- 如果 `current` 不是 `nullptr`，说明还有节点需要处理：
- 交换 `prev` 和 `current` 的数据域：

    if (prev != nullptr) {
        std::swap(prev->data, current->data);
    }

- 将 `prev` 移动到下一个节点，`current` 移动到 `current->next`：

    prev = current;
    current = current->next;

- 当 `current` 为 `nullptr` 时，循环结束。

最后，更新头节点为原链表的最后一个节点，即新的第一个节点：

if (prev != nullptr) {
    head = prev;
}

以下是完整的逆置链表函数：

void reverseList(Node* &head) {
    // ... 具体实现如上
}