面试题：C语言指针的指针与复杂数据结构

Question

假设有一个链表，链表的每个节点包含一个指针，该指针指向一个包含多个整数的数组（数组大小不定）。使用指针的指针来实现链表节点的插入和删除操作，同时实现对链表中所有数组元素的求和功能。要求提供完整的代码实现，并分析时间和空间复杂度。

Answer 1

#include <iostream>
#include <vector>

// 定义链表节点
struct ListNode {
    std::vector<int>* arr;
    ListNode* next;
    ListNode(std::vector<int>* a) : arr(a), next(nullptr) {}
};

// 在链表头部插入节点
void insertAtHead(ListNode** head, std::vector<int>* arr) {
    ListNode* newNode = new ListNode(arr);
    newNode->next = *head;
    *head = newNode;
}

// 删除链表中的指定节点
void deleteNode(ListNode** head, ListNode* nodeToDelete) {
    if (*head == nodeToDelete) {
        *head = nodeToDelete->next;
        delete nodeToDelete->arr;
        delete nodeToDelete;
        return;
    }
    ListNode* current = *head;
    while (current->next != nodeToDelete && current->next != nullptr) {
        current = current->next;
    }
    if (current->next == nodeToDelete) {
        current->next = nodeToDelete->next;
        delete nodeToDelete->arr;
        delete nodeToDelete;
    }
}

// 计算链表中所有数组元素的和
int sumAllElements(ListNode* head) {
    int sum = 0;
    ListNode* current = head;
    while (current != nullptr) {
        for (int num : *(current->arr)) {
            sum += num;
        }
        current = current->next;
    }
    return sum;
}

// 释放链表内存
void freeList(ListNode* head) {
    ListNode* current = head;
    ListNode* nextNode;
    while (current != nullptr) {
        nextNode = current->next;
        delete current->arr;
        delete current;
        current = nextNode;
    }
}

时间复杂度分析

1. 插入操作（insertAtHead）：在链表头部插入节点，只需更新指针，时间复杂度为 $O(1)$。
2. 删除操作（deleteNode）：需要遍历链表找到要删除的节点，平均情况下时间复杂度为 $O(n)$，其中 $n$ 是链表的长度。
3. 求和操作（sumAllElements）：需要遍历链表的每个节点，并对每个节点中的数组进行遍历，时间复杂度为 $O(n \cdot m)$，其中 $n$ 是链表的长度，$m$ 是数组平均长度。

空间复杂度分析

1. 链表本身：空间复杂度为 $O(n)$，其中 $n$ 是链表的长度，因为需要存储 $n$ 个节点。
2. 数组：空间复杂度取决于数组中元素的数量，假设所有数组元素总数为 $N$，则空间复杂度为 $O(N)$。 综合起来，总的空间复杂度为 $O(n + N)$。