链表循环及差集相关算法题|判断循环双链表是否对称|两循环单链表合并成循环链表|使双向循环链表有序|单循环链表改双向循环链表|两链表的差集(C)

判断循环双链表是否对称

设计一个算法用于判断带头节点的循环双链表是否对称

算法思想

让left从左向右扫描，right从右向左扫描，直到它们指向同一个节点：left == right
或相邻left->next == right，或right->prev == left，为止
若它们所指节点值相同，则继续下去，否则返回false，若比较全部相等，则返回true

当节点个数是奇数

直到left == right时，循环结束

当节点个数是偶数

直到发生交错后，right的next指向left，循环结束

bool Symmetry(DLinkList &L)
{// 初始化左右指针，指向链表的首尾节点DNode* left = L->next, *right = L->prev;// 当左右指针未相遇，且未交错while (left != right && right->next != left){// 如果左右数据相等if (left->data == right->data){// 左指针右移left = left->next;// 右指针左移right = right->prev;}// 如果不相等，则链表不对称elsereturn false;}// 循环结束，说明链表对称return true;
}

两循环单链表合并成循环链表

有两个循环单链表，链表头指针分别为h1和h2，编写一个函数将链表h2链接到链表h1之后，要求连接后的链表仍保持循环链表的形式

算法思想

先找到两个链表的尾指针，将第一个链表的尾指针与第二个链表的头指针链接起来，再使之成为循环链表

找尾

将cur1的next指向h2

将cur2的next指向h1

构成循环链表

LinkList Link(LinkList &h1, LinkList &h2)
{// 创建两个工作指针cur1和cur2LNode* cur1, cur2;cur1 = h1;// 寻找h1的尾节点while (cur1->next != h1){cur1 = cur1->next;}cur2 = h2;// 寻找h2的尾节点while (cur2->next != h2){cur2 = cur2->next;}// 将h2链接到h1之后cur1->next = h2;// 令h2的尾节点指向h2cur2->next = h1;return h1;
}

使双向循环链表有序

已知一双向循环链表，从第二个节点至表尾递增有序
将第一个节点删除并插入表中适当位置，使整个链表递增有序

算法思想

应该先将第一节点从链表上摘下来，再将其插入到链表中相应的位置，由于是双向链表，不必像单链表那样插入节点的前驱

断开tmp和链表
cur的prev指向L的prev

L的prev的next指向cur

查插入位置
直到cur的data大于等于x后停下，之后把原第一个节点插在cur的前一个位置
tmp的next指向cur，tmp的prev指向cur的prev

cur的前一个的next指向tmp，cur的prev指向tmp

void DInsert(DLinkList &L)
{// tmp暂存第一节点的指针DNode* tmp = L;int x = L->data;// 将第一个节点从链表上摘下DNode* cur = L->next;cur->prev = L->prev;L->prev->next = cur;// 查插入位置while (cur && cur->data < x){cur = cur->next;}// 插入原第一节点tmp->next = cur;tmp->prev = cur->prev;cur->prev->next = tmp;cur->prev = tmp;
}

单循环链表改双向循环链表

假设一个单循环链表，其节点含有三个域，prev，data，next，prev为空指针，next指向后继节点
将此表改为双向循环链表

cur的next的prev指向cur
直到cur的next的prev不为空

cur正好遍历完链表

算法思想

关键是控制每个节点均置上指向前驱的指针，而且每个节点的前驱指针置且仅置一次

void StoDouble(LinkList &L)
{LNode* cur = L;while (cur->next->prev == NULL){cur->next->prev = cur;cur = cur->next;}
}

两链表的差集

已知递增有序的单链表A，B分别存储了一个集合，请设计算法以求出两个集合A和B的差集，A-B，并以同样的方式存储，同时返回该集合的元素个数

算法思想

在A中删除A和B中共有的元素，由于是单链表，删除节点要记住被删除节点的前驱，两个链表都开始遍历，直到一个链表遍历结束

void Difference(LinkList &A, LinkList &B, int* n)
{// cura和curb分别是链表A和B的工作指针LNode* cura = A->next;LNode* curb = B->next;// prev为链表A中cur所指节点的前一个节点LNode* prev = A;while (cura && curb){if (cura->data < curb->data){prev = cura;cura = cura->next;*n++;}else if (cura->data > curb->data){curb = curb->next;}// 元素值相同的节点，删除else{prev->next = cura->next;LNode* del = cura;cura = cura->next;free(del);}}while (cura){cura = cura->next;*n++;}
}