移除两个双向链表中的重复元素，每个链表中的元素不重复

移除两个双向链表中的重复元素，每个链表中的元素不重复，请给出算法。

ans: 该问题比单向链表要更加复杂一些，必须考虑并更新前向节点的指向情况，具体编码中存在一些难度，加上链表调试相对不容易，因此难度系数略高。

主要思路为：

为每个链表添加哨兵节点，哨兵节点方便操作，因为头节点可能为重复元素
访问链表A的首元素，和链表B的元素依次做对比
- 当对比相等时，
  - 移除B的当前元素，更新B的指向
  - 移除A的当前元素，更新A的指向
  - break B
- 当对比不相等时，
  - 链表B指针依次后移，直到为空
当链表B的指针指向为空时，更新链表A的指针指向，继续对比，直到链表A为空
打印出链表元素，因为是双向链表，必须两个方向打印，方能确保正确。
代码如下，main中运行testList即可

typedef struct Node { //双链节点 定义int data;struct Node *prev, *next;
} DList;void PrintList(DList *head) { // 打印链表，DList *cur = head;while(cur != NULL) { // 正向打印printf("%d ", cur->data);cur = cur->next;if(cur) {printf(" -> ");}}printf(" || ");cur = head;while(cur->next != NULL) { // 寻找尾巴节点cur = cur->next;}while(cur != NULL) { // 反向打印printf("%d", cur->data);cur = cur->prev;if(cur) {printf(" -> ");}}
}void delSameDataNodes(DList **pHead1, DList **pHead2) { // 因会修改head 节点指向，所以必须使用二级指针if(*pHead1 == NULL || *pHead2 == NULL) {return;}DList* dummy1 = (DList *) malloc(sizeof(DList));  // 哨兵节点DList* dummy2 = (DList *) malloc(sizeof(DList));dummy1->next = *pHead1;  // 哨兵节点添加到头节点前面dummy2->next = *pHead2;dummy1->prev = NULL;  // 哨兵节点初始化dummy2->prev = NULL;dummy1->data = 0;dummy2->data = 0;DList* pc1 = *pHead1; // 为每个链表定义前节点，当前节点，后续节点指针DList* pf1 = dummy1;DList* pn1 = pc1->next;DList* pc2 = *pHead2;DList* pf2 = dummy2;DList* pn2 = pc2->next;int dup = 0; // 是否重复指示标志位while(pc1 != NULL) { // 链表A开始循环，逐一元素访问pf2 = dummy2; // 每当链表A访问新元素时， 链表B的3个指针必须从链表头重新开始指向，因pHead2有可能被移除，因此只能用哨兵节点pc2 = pf2->next;pn2 = pc2->next;while(pc2 != NULL) {if(pc1->data != pc2->data) {  // 两个链表元素不等时，链表2继续向后检索，知道链表末端，注意更新3个指针pf2 = pc2;pc2 = pn2;pn2 = (pn2 == NULL)?NULL:pn2->next; // 如果pn2 为空时，不能对其赋值} else {  // 两个链表元素相等时 ，需要设置标志位，跳过当前节点 pc2dup = 1;  // 设置标志位if(pn2) { // 如果pn2 非空时，跳过当前节点，并更新指针，因跳出当前循环，所以此处pc2可以不用设置pf2->next = pn2;pn2->prev = pf2;} else {pf2->next = NULL;}break;}}if(dup == 1) {dup = 0;if(pn1) {pf1->next = pn1;pn1->prev = pf1;pc1 = pn1;  // 此处pc1 必须设置pn1 = pn1->next;} else {pf1->next = NULL;}} else {pf1=pc1;pc1=pn1;pn1 = (pn1 == NULL)?NULL:pn1->next;}}*pHead1 = dummy1->next;*pHead2 = dummy2->next;(*pHead1)->prev = NULL;(*pHead2)->prev = NULL;free(dummy1);dummy1 = NULL;free(dummy2);dummy2 = NULL;
}void add2Tail(DList **head, int data) {DList *node = (DList*) malloc(sizeof(DList));node->data = data;node->next = NULL;node->prev = NULL;if(*head == NULL) {*head = node;} else {DList *cur =*head;while(cur->next!=NULL) {cur = cur->next;}cur->next = node;node->prev = cur;}
}void testList(void){DList *head1 = NULL;DList *head2 = NULL;add2Tail(&head1, 1);add2Tail(&head1, 2);add2Tail(&head1, 3);add2Tail(&head1, 4);add2Tail(&head1, 8);add2Tail(&head1, 9);printf("original list 1: ");PrintList(head1);printf("\n");add2Tail(&head2, 1);add2Tail(&head2, 2);add2Tail(&head2, 4);add2Tail(&head2, 5);add2Tail(&head2, 6);add2Tail(&head2, 7);add2Tail(&head2, 9);printf("original list 2: ");PrintList(head2);printf("\n---------------\n");delSameDataNodes(&head1, &head2);printf("remove duplicate list1: ");PrintList(head1);printf("\n");printf("remove duplicate list2: ");PrintList(head2);printf("\n");
}