1. 打印循环单链表
问题
打印循环单链表
算法思想
- 注意终止条件为
pNode != L
代码
void printCircleList(LinkList L) { printf("------------printf start------------\n"); LinkNode* pNode = L->next; while (pNode != L) { printf("%d ", pNode->data); pNode = pNode->next; } printf("\n------------printf end------------\n"); }
2. 头插法创建循环单链表
问题
建立带头节点的循环单链表
算法思想
- 注意初始化时需将
L->next = L
。
代码
void createCircleList(LinkList& L, ElemType* arr, int arrLength) { L = (LinkNode*)malloc(sizeof(LinkNode)); L->next = L; LinkNode* pNode = NULL; for (int i = 0; i < arrLength; i++) { pNode = (LinkNode*)malloc(sizeof(LinkNode)); pNode->data = arr[i]; // 头插法 pNode->next = L->next; L->next = pNode; } }
2. 尾插法构造循环单链表
问题
创建尾指针指向的循环单链表
算法思想
- 注意更新尾指针
代码
void createTailCircleList(LinkList& L, ElemType* arr, int arrLength) { // 创建头节点 L = (LinkNode*)malloc(sizeof(LinkNode)); L->next = L; // 使用尾插法构建单链表 LinkNode* tailNode = L; LinkNode* tmpNode = NULL; for (int i = 0; i < arrLength; i++) { tmpNode = (LinkNode*)malloc(sizeof(LinkNode)); tmpNode->data = arr[i]; // 尾插法 tmpNode->next = tailNode->next; tailNode->next = tmpNode; // 更新尾指针 tailNode = tmpNode; } }
4.循环单链表反转
问题
将一个带头结点的循环单链表中所有的链接方向反转
算法思想
- 构建新的循环链表
- 依次将旧链表中的结点使用头插法插入新链表
- 注意终止条件
代码
void reverseCircleList(LinkList& L) { // 指向第一个数据节点 LinkNode* pNode = L->next; // 新建一个空的循环链表 L->next = L; LinkNode* tmpNode = NULL; while (pNode != L) { // 保存待插入结点 tmpNode = pNode; // 更新pNode pNode = pNode->next; // 将结点使用头插法插入新的循环链表中 tmpNode->next = L->next; L->next = tmpNode; } }
5. 循环左移k个结点
问题
设计算法将不带头结点的循环单链表左移k个结点
算法思想
不带头结点循环单链表,左移k位后,循环链表中的第k+1个元素将会成为链表中第一个数据节点,所以只需将头结点指向第K+1个结点,就能实现左移k位。
代码
void moveElemCircleList(LinkList& L, int k) { if (L == NULL) return; LinkNode* pNode = L; int count = 1; while (count <= k) { pNode = pNode->next; count++; } // 左移k个结点后,k+1个结点即为循环单链表中第一个数据结点 L = pNode; }
带头结点循环单链表左移
带头节点的循环单链表先把头节点摘下来,链成不带头节点的循环单链表,在不带头节点的循环单链表上操作,最后将链表头结点加入
void moveElemCircleList2(LinkList& L, int k) { // 将头节点取下 LinkNode* pNode = L->next; // 找到链表的最后一个结点 while (pNode->next != L) { pNode = pNode->next; } // 将头结点去掉,此时为不带头结点循环单链表 pNode->next = L->next; // pNode继续指向第一个结点 pNode = pNode->next; int count = 1; // 记住一下前驱节点,方便把头节点加进去 LinkNode* preNode = NULL; while (count <= k) { preNode = pNode; pNode = pNode->next; count++; } // 将头节点加入链表 preNode->next = L; L->next = pNode; }
6. 删除结点p的前驱
问题
设计算法将循环单链表中结点p的直接前驱删除
算法思想
- 先找p的前驱节点,同时保存p前驱的前驱
- 删除p的前驱
代码
void deleteCircleListPreNode(LinkList L, LinkNode* p) { LinkNode* pNode = L->next; LinkNode* preNode = L; // 从pNode开始查找p的前驱结点 while (pNode->next != p) { preNode = pNode; pNode = pNode->next; } // 删除p的前驱结点 preNode->next = pNode->next; free(pNode); }
7.逆置部分单链表
问题
已知一个单链表的头结点,设计算法将表中从i号结点到m号结点构成一个逆置循环链表
算法思想
- 将查找链表中第i个结点的前驱封装为一个函数
- 将单链表中的第i个和第m个结点的前驱取出来;
- 把第i到m结点从单链表中取出来,用头插法插入新的循环单链表中。
代码
查找第i个结点的前驱
LinkNode* getNodePre(LinkList L, int i) { LinkNode* pNode = L->next; LinkNode* preNode = L; int count = 0; while (pNode != NULL) { count++; if (count == i) return preNode; preNode = pNode; pNode = pNode->next; } }
处理单链表及新建循环单链表
LinkList composeCircleList(LinkList L, int i, int m) { LinkNode* preNodeI = getNodePre(L, i); LinkNode* preNodeM = getNodePre(L, m); // 取出第m个结点 LinkNode* pNode = preNodeI->next; // 将原来的单链表链起来 preNodeI->next = preNodeM->next->next; // 将第m个结点的后继置为NULL preNodeM->next->next = NULL; // 新建循环单链表 LinkList circleLst = (LinkNode*)malloc(sizeof(LinkNode)); circleLst->next = circleLst; // 头插法将取出来的单链表插入新的循环单链表 while (pNode != NULL) { LinkNode* tmpNode = pNode; pNode = pNode->next; tmpNode->next = circleLst->next; circleLst->next = tmpNode; } return circleLst; }
8. 循环单链表合并
问题
已知La和Lb分别为两个循环单链表的头结点指针,m和n分别时La和Lb中数据结点的个数,设计时间复杂度最小的算法,将两个链表合并成一个带头结点的循环单链表。
算法思想
- 找到两个链表中的最长链和最短链;
- 依次访问最短链,使用头插法插入较长链中;
代码
void combineCircleList(LinkList La, LinkList Lb, int m, int n) { // 指向较长的链 LinkNode* pShort = m > n ? Lb : La; // 指向较短的链 LinkNode* pLong = m > n ? La : Lb; LinkNode* pNode = pShort->next; LinkNode* tmpNode = NULL; // 依次访问较短链中的数据,并插入较长链中 while (pNode != pShort) { tmpNode = pNode; pNode = pNode->next; // 头插法 tmpNode->next = pLong->next; pLong->next = tmpNode; } // 释放较短链头节点 free(pShort); }
9.带尾指针的循环单链表
思想
当尾部操作比较频繁时,可以在表中设置尾指针,而不设置头指针。这样就避免了频繁的从头结点搜索尾结点的情况。

注意:单链表中头结点不存在前驱,尾结点也不存在后继。但是在循环单链表中,包括头结点和尾结点在内,任意结点都会有前驱和后继。
代码
L 是链表的尾指针
void createTailPointCircleList(LinkList& L, ElemType* arr, int arrLength) { // 创建头节点 L = (LinkNode*)malloc(sizeof(LinkNode)); L->next = L; // 使用尾插法构建单链表 LinkNode* tmpNode = NULL; for (int i = 0; i < arrLength; i++) { tmpNode = (LinkNode*)malloc(sizeof(LinkNode)); tmpNode->data = arr[i]; // 尾插法 tmpNode->next = L->next; L->next = tmpNode; // 更新尾指针 L = tmpNode; } }
输出函数
void printTailList(LinkList L) { // pHead指向头结点 LinkNode* pHead = L->next; // pNode指向头结点的后继 LinkNode* pNode = pHead->next; while (pNode != pHead) { printf("%d ", pNode->data); pNode = pNode->next; } printf("\n--------end-------\n"); }
补充
问题
设计一种数据结构来存储带头结点的循环单链表La和Lb,使得两链表合并的效率尽可能高
算法思想
- La和Lb使用带尾结点指针的循环单链表
- 将La的尾指针指向Lb的第一个数据节点,然后将Lb链的尾结点指针指向La链的结点
代码
void combineCircleList(LinkList& La, LinkList& Lb) { // 指向La的头结点 LinkNode* pHeadLa = La->next; // 指向Lb的头结点 LinkNode* pHeadLb = Lb->next; // La中的尾结点指针指向Lb的第一个数据结点 La->next = pHeadLb->next; // Lb尾结点指针指向La的头结点 Lb->next = pHeadLa; // 释放Lb的头结点 free(pHeadLb); // 修改La的尾指针 La = Lb; }
测试
int arr[] = { 0,1,2,1,0}; int arrLength = 5; LinkList La; createTailPointCircleList(La, arr, arrLength); printTailList(La); LinkList Lb; createTailPointCircleList(Lb, arr, arrLength); combineCircleList(La, Lb); printTailList(La);
