雅虎面试题─有两个双向循环链表A,B,知道其头指针为:pHeadA,pHeadB,请写一函数将两链表中data值相同的结点删除...
时间: 2024-01-22 20:19:24 浏览: 22
这道题可以分为两个步骤:
1. 遍历链表A,将每个结点的值存入一个集合中;
2. 遍历链表B,如果当前结点的值在集合中出现过,则删除该结点。
具体实现可以参考以下代码:
```
typedef struct Node {
int data;
struct Node *prev;
struct Node *next;
} Node;
void deleteNodesWithSameValue(Node *pHeadA, Node *pHeadB) {
// Step 1: Traverse list A and store all values in a set
unordered_set<int> valueSet;
Node *pNodeA = pHeadA->next;
while (pNodeA != pHeadA) {
valueSet.insert(pNodeA->data);
pNodeA = pNodeA->next;
}
// Step 2: Traverse list B and delete nodes with the same value as in the set
Node *pNodeB = pHeadB->next;
while (pNodeB != pHeadB) {
if (valueSet.count(pNodeB->data) > 0) {
pNodeB->prev->next = pNodeB->next;
pNodeB->next->prev = pNodeB->prev;
Node *temp = pNodeB;
pNodeB = pNodeB->next;
delete temp;
} else {
pNodeB = pNodeB->next;
}
}
}
```
需要注意的是,由于链表是双向循环链表,所以在删除某个结点时需要同时修改其前驱和后继的指针,否则会破坏链表的结构。