面试题：C语言指向结构体指针的复杂操作

Question

定义一个链表结构体struct Node { int data; struct Node *next; }; 编写一个函数，该函数接收一个指向链表头节点的指针，将链表逆序，并返回逆序后的链表头节点指针。要求使用指向结构体的指针进行操作，且代码要处理好内存释放等情况。

Answer 1

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

// 定义链表结构体
struct Node {
    int data;
    struct Node *next;
};

// 函数声明
struct Node* reverseList(struct Node* head);

// 主函数
int main() {
    // 构建一个简单链表 1 -> 2 -> 3
    struct Node* head = (struct Node*)malloc(sizeof(struct Node));
    head->data = 1;
    struct Node* node2 = (struct Node*)malloc(sizeof(struct Node));
    node2->data = 2;
    struct Node* node3 = (struct Node*)malloc(sizeof(struct Node));
    node3->data = 3;
    head->next = node2;
    node2->next = node3;
    node3->next = NULL;

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

    // 打印逆序后的链表
    struct Node* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        struct Node* temp = current;
        current = current->next;
        free(temp);
    }
    printf("NULL\n");

    return 0;
}

// 逆序链表函数
struct Node* reverseList(struct Node* head) {
    struct Node* prev = NULL;
    struct Node* current = head;
    struct Node* next = NULL;

    while (current != NULL) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }

    return prev;
}

1. 链表结构体定义：
   • 定义了一个链表结构体struct Node，包含一个整数data用于存储数据，以及一个指向下一个节点的指针next。
2. 函数声明：
   • struct Node* reverseList(struct Node* head);声明了逆序链表的函数。
3. 主函数：
   • 构建了一个简单的链表1 -> 2 -> 3。
   • 调用reverseList函数逆序链表。
   • 打印逆序后的链表，并在打印过程中释放每个节点的内存。
4. 逆序链表函数reverseList：
   • 使用三个指针prev、current和next。
   • prev初始化为NULL，current初始化为链表头节点head，next用于临时保存current的下一个节点。
   • 通过循环，将current节点的next指针指向前一个节点prev，并不断更新prev和current指针，最终返回新的链表头节点prev。