已知A，B和C为三个非递减有序的线性表，均以单链表作为存储结构。现要求对A表作如下操作：删去那些既在B表中出现又在C表中出现的元素。试对单链表编写实现上述操作的算法，并释放A表中的无用结点空间。- 输入说明：第一行输入3个正整数m, n, p（m,n,p <= 100），用空格分开，表示三个线性表中的元素个数，其后3行依次输入A,B,C表中的元素。- 输出说明：输出实现上述操作后的A表。- 测试输入：8 5 6 1 2 3 4 5 6 6 7 2 3 5 9 12 2 4 5 6 12 13 - 预期输出：1 3 4 6 6 7

<think>好的，我现在需要解决这个问题：删除单链表A中既出现在B表又出现在C表中的元素。首先，我得仔细理解题目要求。题目说A、B、C都是非递减有序的线性表，用单链表存储。我要做的是，遍历A表，找到那些同时存在于B和C中的元素，把它们从A中删除，并且释放空间。 首先，我得想如何高效地找到这些共同元素。因为三个表都是有序的，可以利用有序的特性来优化查找过程。比如，对于每个元素x在A中，我需要检查x是否同时存在于B和C中。如果存在，则删除A中的这个节点。 那么具体步骤应该怎样呢？可能的话，先找出B和C的交集，也就是那些同时在B和C中的元素。然后遍历A，如果当前元素在这个交集里，就删除。这样可能更高效，因为只需要遍历A一次，同时检查是否在交集集合中。 如何找到B和C的交集呢？因为B和C都是有序的，可以用双指针的方法来找出它们的共同元素。例如，同时遍历B和C，比较当前节点的值，如果相等，则记录下来，作为交集中的一个元素，然后两个指针都后移。如果B当前的值小，则B指针后移，否则C指针后移。这样可以在O(n+p)的时间复杂度内完成，其中n和p是B和C的长度。这种方法比暴力查找更高效。 接下来，将B和C的交集元素存储在一个数据结构中，比如哈希表或者数组，方便快速查找。因为元素可能重复吗？题目中的例子，比如输入中的B和C是否有重复？例如，B是2 3 5 9 12，C是2 4 5 6 12 13，他们的交集是2、5、12。注意，虽然B中的元素不重复，题目中的输入可能是否允许重复？题目描述中的“非递减有序”可能允许重复的元素存在。例如，A中的元素有6出现两次，所以可能重复。但B和C的交集要考虑元素的值，而不管出现的次数。例如，只要元素值出现在B和C中至少一次，就属于交集。所以，不管B或C中有多少个该元素，只要存在即可。 因此，在求B和C的交集时，只需要记录所有同时出现在两个表中的元素值，但要注意可能会有重复的值。例如，假设B中有两个5，C中有一个5，那么交集应该包含5，但次数可能不是关键，因为我们要在A中删除所有这样的元素。例如，不管交集元素出现多少次，只要A中的元素值在交集中，就删除。 所以，B和C的交集应该是一个集合，包含所有同时存在的元素值，不管次数。这样，在遍历A时，每个元素的值如果在交集中，则删除。 那么步骤应该是： 1. 将链表B和链表C转换为有序数组，或者直接遍历链表，用双指针法求它们的交集集合。例如，得到集合D，其中的元素是同时在B和C中出现的值。 2. 遍历链表A，删除所有值在集合D中的节点，并释放空间。 现在问题转化为如何高效实现这两个步骤，尤其是如何在单链表中删除节点。 接下来，针对每个步骤详细思考： 首先是求B和C的交集。假设B和C都是有序的，且可能包含重复元素。例如，B和C的链表节点是按非递减顺序排列的。这时，求它们的交集可以采用类似合并有序链表的方法，但只记录相等的元素。 例如，初始化两个指针pB和pC，分别指向B和C的头结点。然后循环比较它们的值： - 如果pB的值等于pC的值，就将该值加入集合D，然后pB和pC都移动到下一个节点。但是需要注意处理重复的情况。例如，B中的元素可能有多个相同的值，比如B中有两个2，C中有三个2，这时候他们的交集应该包含2，但如何避免多次记录？或者是否允许重复？比如，当求交集时，是否需要将重复的值多次记录？ 根据问题要求，我们需要删除A中所有同时在B和C中的元素，因此，对于每个元素x在A中，如果x存在于B和C的交集中，不管出现的次数如何，都要删除。所以，集合D应该是一个包含所有在B和C中出现过的元素的集合，每个元素只需要出现一次即可。例如，即使B和C的交集中有多个相同的元素，只需要记录一次，因为判断时只要值存在即可。例如，集合D的结构应该是一个无序的、不重复的集合，比如哈希集合，这样查询的时间是O(1)。 所以，在求B和C的交集时，可以用双指针的方法，同时记录不重复的元素。例如，当找到相等的元素时，将其加入集合，然后移动指针直到跳过所有相同的元素，以避免重复处理。 比如，当pB->data等于 pC->data时，将该值加入集合D。然后，移动pB直到下一个不同的值，同时移动pC直到下一个不同的值。这样可以避免重复元素多次处理，从而保证集合D中的元素是唯一的。或者，也可以在加入集合时自动去重，因为集合的特性就是元素唯一。比如，每次遇到相等的元素时，不管是否已经存在，都添加到集合中，但由于集合的性质，重复添加同一个值不会有影响。所以，可能更简单的做法是，不管重复，直接添加，而集合自动去重。例如，当B和C的交集元素有重复时，比如B中有两个5，C中有三个5，那么双指针方法在遇到第一个5时，会处理，然后可能继续遇到其他5。这时候，我们需要将这些情况处理，确保所有相同的元素都被考虑进去，但集合D只需要保存不同的元素。 或者，是否应该允许集合D中包含重复？例如，假设B和C的交集中有多个相同的元素，比如B和C都包含多个5，那么是否需要将每个5都加入集合？或者，只要有一个5存在即可？ 根据问题要求，当A中的元素x等于5时，不管出现的次数，都要被删除。所以，集合D只需要包含所有在B和C中都存在的不同元素的值。例如，当x的值存在于D中时，无论出现多少次，A中的x节点都会被删除。所以，集合D只需要保存不同的值，不需要重复记录。因此，在求交集时，可以记录所有不同的共同元素的值，而无需考虑次数。 所以，求B和C的交集的步骤可以是： - 初始化两个指针pB和pC，分别指向B和C的头结点。 - 当pB和pC都不为空时： a. 如果pB->data < pC->data，则pB后移。 b. 如果pB->data > pC->data，则pC后移。 c. 如果相等，则将该值加入集合D，然后pB和pC都后移。同时，这里可能需要处理重复元素的情况。例如，当B和C中存在多个相同的值，是否需要跳过所有相同的元素？例如，假设B中的当前值是2，有多个2，而C中的当前值也是2。此时，如果只是移动一次，可能会漏掉后面的相同元素。但此时，我们只需要记录该值存在于交集中即可，所以只需要记录一次。因此，当pB和pC的值相等时，只需要将该值加入集合，然后移动指针。此时，如果后续还有相同的元素，可能需要处理，但这是否必要？ 例如，B的链表为2->2->3，C的链表为2->3->3。此时，他们的交集是2和3。使用双指针法，当比较第一个2和第一个2时，将2加入D。然后pB和pC都移动到下一个节点。此时，pB的节点是2，pC的节点是3。这时候pB的值（2）小于pC的值（3），所以pB后移。此时，pB指向3，pC指向3，此时相等，将3加入D。所以，最终D包含2和3，这正是正确的交集。所以，不需要处理重复元素，双指针法自然能处理这种情况，因为当遇到相同的元素时，只需要移动一次指针即可，而不管后面是否有重复的值。此时，只要该值存在于B和C中，就会被加入D，且D是集合，自动去重。 或者，是否可能出现这样的情况：比如B中有元素2，3，5，而C中有元素2，2，5。此时，双指针法的第一次比较，pB和pC都指向2，此时加入D。然后pB移动到3，pC移动到第二个2。此时，pB的3大于pC的2，所以pC移动到下一个节点，此时pC指向5。此时，pB是3，pC是5，所以pB移动到5。此时，两者都指向5，加入D。所以最终D包含2和5，这是正确的交集。所以，双指针法在这种情况下没有问题。 综上，求B和C的交集可以通过双指针法遍历两个链表，每次比较当前元素的值，相等则加入集合D，并移动两个指针；否则移动较小的那个指针。这样，时间复杂度是O(n + p)，其中n和p是B和C的长度。得到的集合D中的元素是B和C的交集，且元素唯一。 接下来，处理链表A，删除所有值在集合D中的节点，同时释放空间。这里需要注意单链表的删除操作。因为单链表的删除需要找到前驱节点，所以可以采用双指针的方法，记录当前节点和前驱节点。如果当前节点的值在D中，则删除该节点，并调整指针。否则，前驱指针和当前指针都后移。 例如，初始化pre为NULL，cur为头结点。然后遍历链表： - 如果cur的值在D中，则删除cur节点。此时，如果pre不存在（即删除头结点），则头结点后移。否则，pre->next指向cur->next。然后释放cur节点，cur更新为pre->next（或头结点的新值）。 - 否则，pre变为cur，cur后移。 这样，遍历整个链表的时间复杂度是O(m)，其中m是A的长度。而每次检查cur的值是否在D中的时间是O(1)，假设集合D用哈希集合实现。 综上，整个算法的时间复杂度是O(n + p + m)，这应该是可行的。 现在，考虑如何用代码实现。需要完成以下几个步骤： 1. 读取输入。第一行是m, n, p。然后是三个行的元素，分别构成A、B、C三个链表。注意，输入的每个元素都是非递减有序的，所以构造链表时应该保持顺序。但题目输入是否正确可能需要假设是正确的，用户会按照非递减的顺序输入，所以代码中不需要验证。 2. 构造三个链表：A、B、C。每个链表都是单链表，按照输入顺序构造。例如，输入的A的元素是按非递减顺序排列的，所以构造链表时按照输入顺序依次添加节点即可。例如，输入的A元素可能是1 2 3 4 5 6 6 7，则构造链表时节点顺序为1→2→3→4→5→6→6→7。 3. 求B和C的交集集合D。用上述的双指针法遍历B和C链表，找到共同元素，存入哈希集合。 4. 遍历链表A，删除所有值在D中的节点，并释放空间。 5. 输出处理后的A链表。 现在，如何具体实现这些步骤？ 首先，链表的构造。每个链表可以用头指针来管理。例如，每个链表的结构是单链表的节点结构，每个节点包含数据域和next指针。 在C语言中，可以定义结构体： struct Node { int data; struct Node *next; }; 然后，对于输入的每个元素，逐个创建节点，并连接到链表的尾部。例如，创建链表A时，依次读入元素，并插入到链表尾部。这里需要维护一个头指针和尾指针，方便插入。 接下来，求B和C的交集。初始化指针pB和pC分别指向B和C的头结点。然后循环比较它们的值： while (pB != NULL && pC != NULL) { if (pB->data < pC->data) { pB = pB->next; } else if (pB->data > pC->data) { pC = pC->next; } else { // 相等，将值加入集合D // 这里可以用一个哈希集合，比如用数组或者哈希表 // 假设用C语言，可以用一个数组来记录存在的元素，或者使用动态结构 // 但由于元素的值范围可能较大，所以使用动态结构更合适，比如哈希表 // 但C语言中没有现成的哈希集合，可能需要自己实现简单的版本，或者用数组保存元素，每次查询时遍历数组。 // 但这样时间复杂度会增加，例如，当D的元素数目为k，那么每次查询需要O(k)时间，总时间复杂度变为O(mk)，如果k较大，可能不高效。 // 为了高效，可能需要使用哈希集合，但C语言中没有内置的，所以这里可能需要用数组存储D中的元素，并且在查询时用二分查找。但这就要求数组是有序的。 // 所以，在求D时，可以维护一个有序的数组，这样在后续查询时可以用二分查找。 int val = pB->data; // 检查是否已经存在数组中，避免重复添加 if (d_size == 0 || d_array[d_size-1] != val) { d_array[d_size++] = val; } pB = pB->next; pC = pC->next; } } 这里假设d_array是一个足够大的数组（比如n和p中的较小者），用来保存不重复的公共元素，并且按递增顺序排列。这样，在后续的查询中，可以用二分查找来判断元素是否在数组中。这样，每个查询的时间是O(logk)，其中k是交集的大小。 但这样处理的话，求交集时得到的数组是有序的，且元素唯一。这样，当处理链表A时，对于每个元素的值x，可以用二分查找在d_array中查找是否存在。 这样，整个算法的时间复杂度是： 求交集：O(n + p) 处理链表A：O(m logk)，其中k是交集的大小。假设k较小，这应该是可以接受的。 或者，如果元素的值范围较小，可以用一个布尔数组作为哈希表，比如如果元素值在某个范围内，比如0到某个最大值，可以用数组下标作为键。例如，假设题目中的元素都是正数，并且最大值不超过某个值（比如题目输入限制中的元素值可能不大，比如测试用例中的元素值不超过一定范围），则可以用数组实现哈希集合。 但题目没有给出元素值的范围，所以可能更安全的是使用动态数组保存交集元素，并排序，然后用二分查找。 所以在实现的时候，假设元素的值可能很大，需要用动态数组保存交集，并保持有序，这样二分查找才可行。 那在求交集的时候，我们需要将得到的元素按升序保存，并且不重复。例如，当遇到相等的元素时，只有当数组的最后一个元素不等于当前值时才添加。 或者，在双指针法中，当找到相等元素时，可以继续移动指针直到元素的值改变，以避免重复。例如： 当pB和pC的当前值相等时，记录该值，并将pB和pC都移动到下一个不同的元素。例如： 当pB->data等于pC->data时，记录该值到D，然后： 循环移动pB，直到pB的值不等于当前值或者链表结束。 同样地，移动pC直到pC的值不等于当前值或者链表结束。这样可以确保每个值只被记录一次，并且D中的元素按顺序排列，没有重复。 例如，假设B是2 2 3，C是2 3 3。那么当pB和pC都指向第一个2时，记录2，然后pB移动到第一个3，pC移动到第一个3。此时，两者相等，记录3，然后pB移动到空，pC移动到第二个3。这样，D中的元素是2和3，没有重复。 所以，改进的双指针法可以处理重复元素，使得D中的元素是不重复且有序的。此时，D中的数组是有序的，可以用二分查找进行存在性判断。 这样，在求交集的代码中可以这样处理： struct Node *pB = B->head; struct Node *pC = C->head; int d_array[100]; // 假设最大可能的交集元素数目不超过100，因为题目中的n和p不超过100 int d_size = 0; while (pB != NULL && pC != NULL) { if (pB->data < pC->data) { pB = pB->next; } else if (pB->data > pC->data) { pC = pC->next; } else { int val = pB->data; // 检查是否已经添加过该值 if (d_size == 0 || d_array[d_size-1] != val) { d_array[d_size++] = val; } // 移动pB到下一个不同的值 while (pB != NULL && pB->data == val) { pB = pB->next; } // 移动pC到下一个不同的值 while (pC != NULL && pC->data == val) { pC = pC->next; } } } 这样，得到的d_array中的元素是严格递增的，并且没有重复。这样，在后续的查找中，可以用二分查找。 例如，对于链表A中的某个元素x，判断x是否在d_array中存在，可以用二分查找。 接下来，处理链表A的删除操作。这里需要注意链表的头结点可能被删除的情况。例如，当链表的第一个元素需要被删除时，头指针需要改变。所以，在遍历时，需要维护前驱节点指针。 具体步骤： struct Node *pre = NULL; struct Node *cur = A->head; while (cur != NULL) { if (binary_search(d_array, 0, d_size-1, cur->data)) { // 需要删除当前节点 if (pre == NULL) { // 删除头节点 A->head = cur->next; free(cur); cur = A->head; } else { pre->next = cur->next; free(cur); cur = pre->next; } } else { pre = cur; cur = cur->next; } } 其中，binary_search函数用来在有序数组d_array中查找是否存在目标值。该函数可以用递归或循环实现。 例如，循环实现的二分查找： int binary_search(int arr[], int left, int right, int target) { while (left <= right) { int mid = left + (right - left)/2; if (arr[mid] == target) { return 1; } else if (arr[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return 0; } 综上，整个算法的思路是： 1. 构造三个链表。 2. 找出B和C的交集元素，保存在有序数组d_array中。 3. 遍历A链表，删除所有在d_array中的元素，并释放空间。 4. 输出处理后的A链表。 现在，需要考虑一些边界情况，例如： - B或C为空链表：此时它们的交集为空，所以A链表不需要删除任何元素。 - A链表中的元素全部需要被删除：此时处理后A链表为空。 例如，测试输入中的情况： 测试输入： 8 5 6 1 2 3 4 5 6 6 7 2 3 5 9 12 2 4 5 6 12 13 B和C的交集是2、5、12。对吗？ 让我们用双指针法分析： B的元素：2,3,5,9,12 C的元素：2,4,5,6,12,13 pB和pC初始指向2和2。相等，所以加入D。然后移动pB和pC到下一个不同的元素： pB移动到3，pC移动到4. 现在pB的3 < pC的4，所以pB移动到5. 比较5和4：5>4，所以pC移动到5. 此时，pB的5等于 pC的5，加入D。然后pB移动到9，pC移动到6. 比较9和6：9>6，所以pC移动到12. 比较9和12：9<12，所以pB移动到12。现在pB的12和pC的12相等，加入D。之后，pB移动到NULL，pC移动到13. 此时循环结束。D中的元素是2、5、12。对吗？ 所以，A中的元素需要删除所有等于2、5、12的元素。原A链表是1 2 3 4 5 6 6 7。删除后的链表应该是1 3 4 6 6 7，这与测试用例的预期输出一致。 那这说明我们的算法是正确的。 现在，关于链表的构造，需要注意输入的每个元素是按非递减顺序排列的，所以构造链表时直接按顺序插入即可。 在释放无用节点时，必须正确调整指针，并释放内存，防止内存泄漏。 综上，整个算法的代码可以这样实现： 首先，构造链表的结构，读取输入，构造三个链表。 然后，求B和C的交集，存储在d_array数组中。 接着，删除A中的元素，并释放空间。 最后，输出处理后的A链表。 现在，在代码实现中需要注意一些细节： 例如，在C语言中，处理链表需要动态分配内存，释放内存时要确保不出现野指针。 另外，在构造链表时，需要逐个读取元素，并创建节点，链接到链表的尾部。 现在，假设输入的三个链表元素都是非递减顺序的，因此构造链表时不需要排序，只需要按输入顺序插入即可。例如，输入的A元素已经有序。 综上，最终的代码应该包括以下步骤： 1. 读取m, n, p的值。 2. 读取三个行的元素，分别构造A、B、C三个链表。 3. 求B和C的交集，存储为有序数组d_array。 4. 遍历A链表，删除所有在d_array中的节点，释放空间。 5. 输出处理后的A链表。 现在，编写代码的大致框架： 例如，在C语言中： #include <stdio.h> #include <stdlib.h> typedef struct Node { int data; struct Node *next; } Node; Node* createLinkedList(int *elements, int length) { if (length == 0) return NULL; Node *head = NULL, *tail = NULL; for (int i = 0; i < length; i++) { Node *newNode = (Node*)malloc(sizeof(Node)); newNode->data = elements[i]; newNode->next = NULL; if (head == NULL) { head = newNode; tail = newNode; } else { tail->next = newNode; tail = newNode; } } return head; } void findCommonElements(Node *B, Node *C, int *d_array, int *d_size) { Node *pB = B, *pC = C; *d_size = 0; while (pB != NULL && pC != NULL) { if (pB->data < pC->data) { pB = pB->next; } else if (pB->data > pC->data) { pC = pC->next; } else { int val = pB->data; // 跳过重复元素 while (pB != NULL && pB->data == val) { pB = pB->next; } while (pC != NULL && pC->data == val) { pC = pC->next; } // 存入d_array，确保不重复 if (*d_size == 0 || d_array[*d_size - 1] != val) { d_array[(*d_size)++] = val; } } } } int binarySearch(int *arr, int left, int right, int target) { while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) { return 1; } else if (arr[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return 0; } void deleteNodes(Node **head, int *d_array, int d_size) { Node *pre = NULL; Node *cur = *head; while (cur != NULL) { if (binarySearch(d_array, 0, d_size - 1, cur->data)) { if (pre == NULL) { *head = cur->next; free(cur); cur = *head; } else { pre->next = cur->next; free(cur); cur = pre->next; } } else { pre = cur; cur = cur->next; } } } void printLinkedList(Node *head) { Node *cur = head; while (cur != NULL) { printf("%d ", cur->data); cur = cur->next; } printf("\n"); } void freeLinkedList(Node *head) { Node *cur = head; while (cur != NULL) { Node *temp = cur; cur = cur->next; free(temp); } } int main() { int m, n, p; scanf("%d %d %d", &m, &n, &p); int *a = (int*)malloc(m * sizeof(int)); for (int i = 0; i < m; i++) { scanf("%d", &a[i]); } Node *A = createLinkedList(a, m); int *b = (int*)malloc(n * sizeof(int)); for (int i = 0; i < n; i++) { scanf("%d", &b[i]); } Node *B = createLinkedList(b, n); int *c = (int*)malloc(p * sizeof(int)); for (int i = 0; i < p; i++) { scanf("%d", &c[i]); } Node *C = createLinkedList(c, p); int d_array[100]; int d_size = 0; findCommonElements(B, C, d_array, &d_size); deleteNodes(&A, d_array, d_size); printLinkedList(A); free(a); free(b); free(c); freeLinkedList(A); freeLinkedList(B); freeLinkedList(C); return 0; } 但是，这里可能存在一些问题。例如，在构造链表时，输入的数组可能已经被释放，但是在free(a)之后，链表节点中的data已经被保存到链表中，所以释放数组不影响链表结构。这应该是没问题的。 测试用例的输入： 8 5 6 1 2 3 4 5 6 6 7 2 3 5 9 12 2 4 5 6 12 13 经过处理后，d_array中的元素应该是2、5、12。链表A中的元素将删除这些值，得到1 3 4 6 6 7，符合预期。 另一个测试情况，例如，如果A中的元素全部需要被删除，例如A是2 5 12，那么处理后链表为空，输出为空行。 综上，该代码应该能够正确处理问题。</think>要解决这个问题，我们需要从单链表A中删除那些同时出现在链表B和链表C中的元素，并释放无用结点的空间。以下是分步解决方案： ### 算法思路 1. **输入处理**：读取三个链表的长度和元素，构建非递减有序的单链表A、B、C。 2. **求交集**：通过双指针法遍历B和C，找到它们的公共元素，存储到有序数组中。 3. **删除操作**：遍历链表A，删除所有值在交集数组中的结点，并释放空间。 4. **输出结果**：输出处理后的链表A。 ### 代码实现 ```c #include <stdio.h> #include <stdlib.h> typedef struct Node { int data; struct Node *next; } Node; // 创建单链表 Node* createLinkedList(int *elements, int length) { Node *head = NULL, *tail = NULL; for (int i = 0; i < length; i++) { Node *newNode = (Node*)malloc(sizeof(Node)); newNode->data = elements[i]; newNode->next = NULL; if (!head) { head = newNode; tail = newNode; } else { tail->next = newNode; tail = newNode; } } return head; } // 求B和C的交集（有序不重复） void findCommonElements(Node *B, Node *C, int *d_array, int *d_size) { Node *pB = B, *pC = C; *d_size = 0; while (pB && pC) { if (pB->data < pC->data) { pB = pB->next; } else if (pB->data > pC->data) { pC = pC->next; } else { int val = pB->data; // 跳过重复值 while (pB && pB->data == val) pB = pB->next; while (pC && pC->data == val) pC = pC->next; // 保存唯一值 if (*d_size == 0 || d_array[*d_size - 1] != val) { d_array[(*d_size)++] = val; } } } } // 二分查找 int binarySearch(int *arr, int left, int right, int target) { while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) return 1; else if (arr[mid] < target) left = mid + 1; else right = mid - 1; } return 0; } // 删除A中的目标结点 void deleteNodes(Node **head, int *d_array, int d_size) { Node *pre = NULL, *cur = *head; while (cur) { if (binarySearch(d_array, 0, d_size - 1, cur->data)) { if (!pre) { // 删除头结点 *head = cur->next; free(cur); cur = *head; } else { pre->next = cur->next; free(cur); cur = pre->next; } } else { pre = cur; cur = cur->next; } } } // 输出链表 void printList(Node *head) { Node *cur = head; while (cur) { printf("%d ", cur->data); cur = cur->next; } printf("\n"); } // 释放链表内存 void freeList(Node *head) { Node *cur = head; while (cur) { Node *tmp = cur; cur = cur->next; free(tmp); } } int main() { int m, n, p; scanf("%d %d %d", &m, &n, &p); int *A_elements = (int*)malloc(m * sizeof(int)); for (int i = 0; i < m; i++) scanf("%d", &A_elements[i]); Node *A = createLinkedList(A_elements, m); int *B_elements = (int*)malloc(n * sizeof(int)); for (int i = 0; i < n; i++) scanf("%d", &B_elements[i]); Node *B = createLinkedList(B_elements, n); int *C_elements = (int*)malloc(p * sizeof(int)); for (int i = 0; i < p; i++) scanf("%d", &C_elements[i]); Node *C = createLinkedList(C_elements, p); int common[100], commonSize; findCommonElements(B, C, common, &commonSize); deleteNodes(&A, common, commonSize); printList(A); // 释放内存 free(A_elements); free(B_elements); free(C_elements); freeList(A); freeList(B); freeList(C); return 0; } ``` ### 算法分析 1. **时间复杂度**： - 求交集：$$O(n + p)$$，其中n和p分别为B和C的长度。 - 删除结点：$$O(m \log k)$$，其中m为A的长度，k为交集元素个数。 2. **空间复杂度**：$$O(k)$$，存储交集元素的数组。 该算法高效地利用了有序链表的特性，通过双指针和二分查找优化了性能，确保在合理时间内完成操作。