面试题：C语言双向链表的复杂操作

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

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

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

// 在链表头部插入节点
void insertAtHead(struct DNode** head, int value) {
    struct DNode* newNode = createNode(value);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    newNode->next = *head;
    (*head)->prev = newNode;
    *head = newNode;
}

// 删除指定节点
void deleteNode(struct DNode** head, struct DNode* delNode) {
    if (delNode == NULL) return;
    if (*head == delNode) {
        *head = delNode->next;
    }
    if (delNode->prev != NULL) {
        delNode->prev->next = delNode->next;
    }
    if (delNode->next != NULL) {
        delNode->next->prev = delNode->prev;
    }
    free(delNode);
}

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

// 合并两个有序的双向链表为一个新的有序双向链表
struct DNode* mergeSortedDLL(struct DNode* head1, struct DNode* head2) {
    struct DNode dummy;
    dummy.prev = NULL;
    dummy.next = NULL;
    struct DNode* tail = &dummy;
    while (head1 != NULL && head2 != NULL) {
        if (head1->data <= head2->data) {
            tail->next = head1;
            head1->prev = tail;
            tail = head1;
            head1 = head1->next;
        } else {
            tail->next = head2;
            head2->prev = tail;
            tail = head2;
            head2 = head2->next;
        }
    }
    if (head1 != NULL) {
        tail->next = head1;
        head1->prev = tail;
    }
    if (head2 != NULL) {
        tail->next = head2;
        head2->prev = tail;
    }
    return dummy.next;
}

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

int main() {
    struct DNode* head1 = NULL;
    struct DNode* head2 = NULL;

    insertAtHead(&head1, 1);
    insertAtHead(&head1, 3);
    insertAtHead(&head1, 5);

    insertAtHead(&head2, 2);
    insertAtHead(&head2, 4);
    insertAtHead(&head2, 6);

    printf("链表1: ");
    printDLL(head1);

    printf("链表2: ");
    printDLL(head2);

    struct DNode* mergedHead = mergeSortedDLL(head1, head2);
    printf("合并后的有序链表: ");
    printDLL(mergedHead);

    reverseDLL(&mergedHead);
    printf("逆序后的链表: ");
    printDLL(mergedHead);

    return 0;
}
星途面试题库

面试题：C语言双向链表的复杂操作

知识考点

面试题答案
