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

// 定义链表节点结构体
typedef struct ListNode {
    int data;
    struct ListNode *next;
} ListNode;

// 函数声明
ListNode* reverseList(ListNode* head);

// 辅助函数：创建新节点
ListNode* createNode(int data) {
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    if (newNode == NULL) {
        exit(1); // 分配内存失败，退出程序
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 辅助函数：打印链表
void printList(ListNode* head) {
    ListNode* current = head->next; // 跳过头节点
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

// 主函数
int main() {
    // 创建带头节点的单链表
    ListNode* head = createNode(0); // 头节点，不存放数据
    head->next = createNode(1);
    head->next->next = createNode(2);
    head->next->next->next = createNode(3);
    head->next->next->next->next = createNode(4);

    // 打印原始链表
    printf("Original list: ");
    printList(head);

    // 逆置链表
    head = reverseList(head);

    // 打印逆置后的链表
    printf("Reversed list: ");
    printList(head);

    return 0;
}

// 函数定义：逆置链表
ListNode* reverseList(ListNode* head) {
    ListNode *prev = NULL, *current = head->next, *next = NULL;
    while (current != NULL) {
        next = current->next; // 保存下一个节点
        current->next = prev; // 反转当前节点的指针
        prev = current; // 移动prev指针
        current = next; // 移动current指针
    }
    head->next = prev; // 将头节点的next指向新的头节点
    return head;
}
