C语言实现给定一个带头结点的单链表，编写算法将其原地逆置。所谓“原地”是指空间复杂度为O(1)。 测试用例 输入：5 1 3 5 7 9 输出:9 7 5 3 1

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

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

// 创建带头结点的单链表
Node* createLinkedList(int n) {
    Node* head = (Node*)malloc(sizeof(Node)); // 头结点
    Node* p = head; // 指向尾结点的指针
    for (int i = 0; i < n; i++) {
        int data;
        scanf("%d", &data);
        Node* node = (Node*)malloc(sizeof(Node)); // 新结点
        node->data = data;
        node->next = NULL;
        p->next = node;
        p = node;
    }
    return head;
}

// 原地逆置链表
void reverseLinkedList(Node* head) {
    if (head == NULL || head->next == NULL) return; // 空链表或只有头结点
    Node* p = head->next; // 第一个结点
    Node* q = p->next; // 第二个结点
    p->next = NULL; // 第一个结点成为新的尾结点
    while (q != NULL) {
        Node* r = q->next; // 保存下一个结点
        q->next = p; // 反转指针
        p = q; // 移动指针
        q = r; // 移动指针
    }
    head->next = p; // 头结点的 next 指向新的头结点
}

// 输出链表
void printLinkedList(Node* head) {
    Node* p = head->next; // 第一个结点
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

int main() {
    int n;
    scanf("%d", &n);
    Node* head = createLinkedList(n);
    reverseLinkedList(head);
    printLinkedList(head);
    return 0;
}