面试题：C语言双向链表的删除与反转

Question

用C语言实现一个双向链表，并编写两个函数，一个用于删除双向链表中指定值的节点，另一个用于反转双向链表。双向链表节点结构定义为：struct DNode { int data; struct DNode* prev; struct DNode* next; }; 删除函数原型为：void deleteNode(struct DNode** head, int value); 反转函数原型为：void reverseDList(struct DNode** head); head为双向链表头指针的指针，value为要删除节点的数据值。

Answer 1

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

// 双向链表节点结构定义
struct DNode {
    int data;
    struct DNode* prev;
    struct DNode* next;
};

// 创建新节点
struct DNode* createNode(int data) {
    struct DNode* newNode = (struct DNode*)malloc(sizeof(struct DNode));
    newNode->data = data;
    newNode->prev = newNode->next = NULL;
    return newNode;
}

// 删除双向链表中指定值的节点
void deleteNode(struct DNode** head, int value) {
    struct DNode* current = *head;
    while (current != NULL && current->data != value) {
        current = current->next;
    }
    if (current == NULL) {
        return;
    }
    if (current->prev != NULL) {
        current->prev->next = current->next;
    } else {
        *head = current->next;
    }
    if (current->next != NULL) {
        current->next->prev = current->prev;
    }
    free(current);
}

// 反转双向链表
void reverseDList(struct DNode** head) {
    struct DNode* temp = NULL;
    struct DNode* current = *head;
    while (current != NULL) {
        temp = current->prev;
        current->prev = current->next;
        current->next = temp;
        current = current->prev;
    }
    if (temp != NULL) {
        *head = temp->prev;
    }
}

// 打印双向链表
void printDList(struct DNode* head) {
    struct DNode* current = head;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

// 释放链表内存
void freeDList(struct DNode* head) {
    struct DNode* current = head;
    struct DNode* next;
    while (current != NULL) {
        next = current->next;
        free(current);
        current = next;
    }
}

int main() {
    struct DNode* head = createNode(1);
    struct DNode* node2 = createNode(2);
    struct DNode* node3 = createNode(3);
    head->next = node2;
    node2->prev = head;
    node2->next = node3;
    node3->prev = node2;

    printf("Original list: ");
    printDList(head);

    deleteNode(&head, 2);
    printf("List after deletion: ");
    printDList(head);

    reverseDList(&head);
    printf("List after reversal: ");
    printDList(head);

    freeDList(head);
    return 0;
}