面试题：C++指针运算在复杂数据结构中的应用

Question

设计一个双向链表的数据结构，每个节点包含一个`int`类型的数据和两个指针，分别指向前一个节点和后一个节点。要求实现一个函数，该函数接收链表头指针，通过指针运算找到链表中间节点（如果链表长度为偶数，返回中间两个节点的前一个），并返回该节点的指针。请用C++代码实现这个数据结构和函数，并详细阐述在实现过程中指针运算的逻辑以及可能遇到的指针相关问题（如空指针、野指针等）如何处理。

Answer 1

#include <iostream>

// 定义双向链表节点
struct DoubleListNode {
    int data;
    DoubleListNode* prev;
    DoubleListNode* next;
    DoubleListNode(int val) : data(val), prev(nullptr), next(nullptr) {}
};

// 找到双向链表中间节点的函数
DoubleListNode* findMiddleNode(DoubleListNode* head) {
    if (head == nullptr) {
        return nullptr;
    }
    DoubleListNode* slow = head;
    DoubleListNode* fast = head;

    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }

    return slow;
}

指针运算逻辑

1. 快慢指针初始化：定义两个指针 slow 和 fast，都初始化为链表头指针 head。
2. 移动快慢指针：slow 每次移动一步，fast 每次移动两步。这样，当 fast 到达链表末尾时，slow 正好在链表中间位置（如果链表长度为偶数，slow 指向中间两个节点的前一个）。

指针相关问题及处理

1. 空指针处理：在函数开始时，首先检查 head 是否为空指针。如果 head 为空，直接返回 nullptr，避免后续对空指针进行解引用操作导致程序崩溃。
2. 野指针处理：在代码实现过程中，通过合理的指针初始化（如节点构造函数中 prev 和 next 初始化为 nullptr），以及避免非法的指针赋值和释放操作，可以有效避免产生野指针。同时，在遍历链表时，通过检查指针是否为 nullptr（如 while (fast != nullptr && fast->next != nullptr)），确保不会访问到野指针指向的内存区域。