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

Question

用C++ 实现一个双向链表，并完成以下功能： 1. 编写一个函数`void insertAfter(ListNode* node, int newVal)`，在给定节点`node`之后插入一个新节点，新节点的值为`newVal`。 2. 编写一个函数`void reverseList(ListNode*& head)`，将双向链表反转。 双向链表节点结构如下： ```cpp struct ListNode { int val; ListNode *prev; ListNode *next; ListNode(int x) : val(x), prev(NULL), next(NULL) {} }; ```

Answer 1

#include <iostream>

struct ListNode {
    int val;
    ListNode *prev;
    ListNode *next;
    ListNode(int x) : val(x), prev(NULL), next(NULL) {}
};

// 在给定节点node之后插入一个新节点，新节点的值为newVal
void insertAfter(ListNode* node, int newVal) {
    ListNode* newNode = new ListNode(newVal);
    newNode->next = node->next;
    newNode->prev = node;
    if (node->next != nullptr) {
        node->next->prev = newNode;
    }
    node->next = newNode;
}

// 将双向链表反转
void reverseList(ListNode*& head) {
    ListNode* current = head;
    ListNode* temp = nullptr;
    while (current != nullptr) {
        temp = current->prev;
        current->prev = current->next;
        current->next = temp;
        current = current->prev;
    }
    if (temp != nullptr) {
        head = temp->prev;
    }
}

// 辅助函数：打印双向链表
void printList(ListNode* head) {
    ListNode* current = head;
    while (current != nullptr) {
        std::cout << current->val << " ";
        current = current->next;
    }
    std::cout << std::endl;
}

int main() {
    // 构建双向链表 1 <-> 2 <-> 3
    ListNode* head = new ListNode(1);
    ListNode* node2 = new ListNode(2);
    ListNode* node3 = new ListNode(3);
    head->next = node2;
    node2->prev = head;
    node2->next = node3;
    node3->prev = node2;

    std::cout << "Original list: ";
    printList(head);

    insertAfter(node2, 4);
    std::cout << "List after insertion: ";
    printList(head);

    reverseList(head);
    std::cout << "List after reversal: ";
    printList(head);

    return 0;
}