Question

假设长度大于1的循环单链表中，既无头结点也无头指针， p 为指向该链表中某一结点的指针，编写算法删除该结点的前驱结点

Answer 1

问：假设长度大于1的循环单链表中，既无头结点也无头指针， p 为指向该链表中某一结点的指针，编写算法删除该结点的前驱结点

答：你好亲，由于循环单链表没有头指针，因此无法通过遍历链表找到前驱结点。但是，由于循环单链表是一个闭合的环形结构，因此可以通过顺时针遍历链表来找到前驱结点。具体算法如下：1. 首先判断链表长度是否大于1，如果不大于1，则无法删除前驱结点，直接返回。2. 如果链表长度大于1，则需要找到指向 p 前驱结点的指针 prev，可以通过顺时针遍历链表来寻找 prev，具体实现如下： - 初始化指针 prev 指向链表中最后一个结点。 - 从链表中的最后一个结点开始，通过指针 prev 顺时针遍历链表，直到 prev->next==p。 - 如果在遍历过程中找到了 p 的前驱结点，则跳出循环，否则 prev 指向链表中最后一个结点。3. 如果找到了 p 的前驱结点 prev，则可以通过 prev->next=p->next 将其从链表中删除。4. 如果没有找到 p 的前驱结点，则说明 p 是链表中的第一个结点，此时需要将链表的尾结点的指针指向 p->next，并将 p 从链表中删除。代码实现如下：```

答：void deletePreNode(Node* p) { if (p == NULL || p->next == NULL) { return; } Node* prev = p; while (prev->next != p) { prev = prev->next; if (prev == p) { break; } } if (prev != p) { prev->next = p->next; free(p); } else { Node* tail = prev; while (tail->next != prev) { tail = tail->next; } tail->next = p->next; free(p); }}```

问：已知两个单链表 A 和 B 分别表示两个集合，其元素递增排列，编写算法求出 A 和 B 的交集 C ，要求 C 同样以元素递增的单链表形式存储。

答：亲，可以使用双指针法求解两个有序链表的交集。具体算法步骤如下：1. 分别定义两个指针 pA 和 pB，初始化为链表 A 和 B 的头结点。2. 从链表 A 和 B 的头结点开始，比较 pA 和 pB 所指向的结点的值，如果 pA 的值小于 pB 的值，则将 pA 指向下一个结点；如果 pB 的值小于 pA 的值，则将 pB 指向下一个结点；如果 pA 和 pB 的值相等，则将该结点插入到交集链表 C 的尾部，并将 pA 和 pB 都指向下一个结点。3. 重复上述操作，直到 pA 或 pB 为空。4. 返回交集链表 C 的头结点。代码实现如下：```Node* intersect(Node* A, Node* B) { Node* pA = A->next; Node* pB = B->next; Node* C = (Node*)malloc(sizeof(Node)); // 创建交集链表 C C->next = NULL; Node* tail = C; // 用于记录交集链表 C 的尾结点

答：while (pA != NULL && pB != NULL) { if (pA->data pB->data) { pA = pA->next; } else if (pA->data > pB->data) { pB = pB->next; } else { Node* node = (Node*)malloc(sizeof(Node)); node->data = pA->data; node->next = NULL; tail->next = node; tail = node; pA = pA->next; pB = pB->next; } } return C;}```