判断循环双链表是否对称
设计一个算法用于判断带头节点的循环双链表是否对称
算法思想
让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++;}
}