C语言手撕实战代码_循环单链表和循环双链表

C语言手撕实战代码_循环单链表和循环双链表

循环单链表习题
1.建立带头结点的循环链表
2.设计一个算法，将一个带有头结点的循环单链表中所有结点的链接方向逆转
3.设计一个算法,将一个循环单链表左移k个结点
4.设计一个算法将循环单链表中的结点p的直接前驱删除
5.设计算法将一个含有数字，字母和其他字符组成的循环链表拆分成为三个循环链表，每条链中只包含一种类型的字符。
6.设计一个算法，将单链表中从第 i 个节点到第 m 个节点之间的节点顺序逆置，并将逆置后的子链表变成一个循环链表
7.已知La和Lb分别为两个循环单链表的头节点指针，m和n分别为La和Lb中数据结点的个数，设计时间复杂度最小的算法将两个链表合并成一个带头的循环单链表
8.创建尾指针指向的循环单链表
9.请设计一种数据结构来存储带头结点指针，m和n分别为La和Lb中数据节点的个数，设计时间复杂度最小的算法将两个链表合并成一个带头的循环单链表。

双链表和循环双链表实践
1.双链表的建立
2.双链表的前趋遍历和后继遍历
3.实践双链表:请你设计一个算法，将带头双向链表中数据结点的原有顺序保存在每个结点的next域中，而prior域将所有结点按照其值从小到大的顺序链接起来
4.实践循环双链表:设以头结点得双向循环链表表示得线性表为L=(a1，a2,a3，…,an)。试写一时间复杂度为o(n)的算法，将L改造为L(a1,a3,an,a4,a2)

循环单链表实践

1.建立带头结点的循环链表

思路:在原有带头结点单链表的基础上，让尾部指向头结点，因为要操作尾部，所以使用尾插法建立。
其实就是用尾插法在结尾处让原本指向空的指针，指向头结点

void creat_cyclelinklist_byinserttail(LinkList &L,int enterArra[],int enterArraLength)
{//先定义头结点L=(LinkNode *)malloc(sizeof(LinkNode));L->next=NULL;//循环尾插结点int index=0; //第一个数组下标LinkList tail=L;while(index<enterArraLength){LinkNode *p=(LinkNode *)malloc(sizeof(LinkNode));p->data= enterArra[index++];tail->next=p;tail=p;}tail->next=L;
}

就是把
tail->next=NULL;改成了tail->next=L;
验证建立带头结点的循环链表，循环12次，看看输出的链表

    int c[8]={1,2,3,4,5,6,7,8};LinkList Lc=NULL;creat_cyclelinklist_byinserttail(Lc, c, 8);int x=12;LinkNode *p=Lc;while (x--) {printf("%d->",p->next->data);p=p->next;}printf("NULL\n");

2.设计一个算法，将一个带有头结点的循环单链表中所有结点的链接方向逆转

思路:循环单链表的逆转其实和单链表的逆转并无差别，还是用pre和cur指针再配一个临时p指针，主要注意一下，最后反转完还是循环的就行。

总结:循环单链表反转=单链表反转+处理头结点反转

void reverse_cryleLinklist(LinkList &Lc)
{LinkNode *cur=Lc->next; //指向第一个元素LinkNode *pre=Lc; //指向头结点LinkNode *p=NULL;while(p!=Lc){p=cur->next;cur->next=pre;pre=cur;cur=p;}     //这里结束，意味着除了头结点之外都反转过来了，即完成了单链表的反转操作Lc->next=pre; //最后一步，完成了头结点的反转
}

3.设计一个算法,将一个循环单链表左移k个结点

左移简单理解就是，原先的循环一遍的顺序是12345,左移两位之后，循环的顺序就是34512.也就是头结点右移

不需要引入新的头结点的方式。
需要找到链表尾部，头结点插入的前一个位置，插入的后一个位置，

找到待插入结点和它的前一个结点。还有最后一个结点，然后将新的头结点插入，将最后一个结点指向第一个结点。

void left_crycle_linklist(LinkList &Lc,int k)
{//找到三个点 pre cur last,记录一个点 first,第一个结点的位置LinkNode *pre=Lc;LinkNode *cur=Lc->next;LinkNode *last=Lc;LinkNode *first=Lc->next;//第一个循环找pre和curwhile (k--) {cur=cur->next;pre=pre->next;}//第二个循环找lastwhile(last->next!=Lc){last=last->next;}//将头结点插入Lc->next=cur;pre->next=Lc;//将最后一个结点连接第一个结点last->next=first;
}

思考:我记得单链表中还是使用反转链表做的，但是循环链表就不用那么复杂。

4.设计一个算法将循环单链表中的结点p的直接前驱删除

思路：给你一个指向p结点的指针P，设置一个寻找指针find，和新的指向p的指针new_p,find指向P的后继的后继。new_p和find构成双指针移动。find再次指向p的时候，new_p就指向了我们的目标，然后进行删除就ok。

5.设计算法将一个含有数字，字母和其他字符组成的循环链表拆分成为三个循环链表，每条链中只包含一种类型的字符。

思路:创建三个循环链表，采用头插法加入链表，重点在于判断三种类型。
数字0的asc码是48，数字0到9是连续的，故9的asc码是48+9=57
大写字母A的asc码是65，故大写字母Z的asc码是65+25=90
小写字母a是asc码是97，故小写字母z的asc码是97+25=122

6.设计一个算法，将单链表中从第 i 个节点到第 m 个节点之间的节点顺序逆置，并将逆置后的子链表变成一个循环链表

逻辑很清晰，先逆置，最后操作形成循环链表
值得注意的是，这个操作之后，m结点之后的结点将无法被访问到。

给出图例:

7.已知La和Lb分别为两个循环单链表的头节点指针，m和n分别为La和Lb中数据结点的个数，设计时间复杂度最小的算法将两个链表合并成一个带头的循环单链表

思路很简单，将较短的循环单链表插入较长的循环单链表中，采用头插法。

注意和第9题联系起来

8.创建尾指针指向的循环单链表

本质就是，尾插法建立循环单链表，记录好最后一个元素，处理好循环。
非常值得注意的是此时La和Lb 是指向最后一个结点，假如你要找到头结点
La->next才是头结点

9.请设计一种数据结构来存储带头结点指针，m和n分别为La和Lb中数据节点的个数，设计时间复杂度最小的算法将两个链表合并成一个带头的循环单链表。

其中pheadLa是这么定义的，pheadLa=Ta->next。

---

双链表和循环双链表实践

1.双链表的建立

使用头插法建立双链表，在插入过程中，先连接插入结点，再更新插入结点的前驱结点和后继结点。注意后继结点一定要判空，否则会访问出界。

typedef  int ElemType;
typedef struct DuLinkNode
{ElemType data;struct DuLinkNode* prior;struct DuLinkNode* next;
}DuLinkNode,*DuLinkList;

void creat_doubleLinklist(DuLinkList &DL, int a[4],int length) //双链表的建立
{//创建一个头结点DL=(DuLinkNode *)malloc(sizeof(DuLinkNode));DL->next=NULL;DL->prior=NULL;DuLinkNode * L=DL;//添加结点for(int i=0;i<length;i++){DuLinkNode * p;p=(DuLinkNode *)malloc(sizeof(DuLinkNode));p->data=a[i];p->next=L->next;   //更新插入结点的后继指针域p->prior=L;   //更新插入结点的前驱指针域L->next=p;    //更新前驱结点的后继指针域if(p->next!=NULL){p->next->prior=p; //更新后继结点的前驱指针域}}
}

2.双链表的前趋遍历和后继遍历

void print_next(DuLinkList DL,int length)  //双链表的后继遍历
{while(length--){printf("%d->",DL->next->data);DL=DL->next;}printf("NULL\n");
}void print_prior(DuLinkList DL,int length)  //双链表的前趋遍历
{while(DL->next!=NULL){DL=DL->next;}while(length--){printf("%d->",DL->data);DL=DL->prior;}printf("NULL\n");
}

3.实践双链表:请你设计一个算法，将带头双向链表中数据结点的原有顺序保存在每个结点的next域中，而prior域将所有结点按照其值从小到大的顺序链接起来

next储存原先顺序，prior储存排序顺序，反向使用单链表的插入排序

关于单链表的插入排序

struct ListNode* insertionSortList(struct ListNode* head) {if (head == NULL) return NULL;  // 检查链表是否为空struct ListNode* L = (struct ListNode*)malloc(sizeof(struct ListNode));L->next = head;struct ListNode* ordermove;             // ordermove起点是头结点struct ListNode* disordermove = head->next; // disordermove起点是第二个元素，因为第一个元素默认有序head->next = NULL;  // 断开链表，只保留第一个元素作为初始有序链表while (disordermove != NULL) {  // 当disordermove遍历完之后循环结束ordermove = L;  // 重置 ordermove 为哑结点 L// 寻找插入点while (ordermove->next != NULL && ordermove->next->val < disordermove->val) {ordermove = ordermove->next;}// 插入 disordermove 到 ordermove 之后struct ListNode* nextDisorder = disordermove->next;  // 记录下一个待排序结点disordermove->next = ordermove->next;ordermove->next = disordermove;// 移动到下一个待排序结点disordermove = nextDisorder;}struct ListNode* sortedHead = L->next;  // 排序后的链表头部free(L);  // 释放哑结点return sortedHead;
}

4.实践循环双链表:设以头结点得双向循环链表表示得线性表为L=(a₁，a₂,a₃，…,a_n)。试写一时间复杂度为o(n)的算法，将L改造为L(a₁,a₃,a_n,a₄,a₂)

首先，创建一个带头结点的循环双链表（采用尾插法方便）

void creat_doublecycleLinklist(DuLinkList &DL, int a[8],int length) //双链表的建立
{//创建一个头结点DL=(DuLinkNode *)malloc(sizeof(DuLinkNode));DL->next=DL;DL->prior=DL;DuLinkNode * cur=DL;//添加结点for(int i=0;i<length;i++){DuLinkNode * p;p=(DuLinkNode *)malloc(sizeof(DuLinkNode));p->data=a[i];p->next=DL;   //更新插入结点的后继指针域p->prior=cur;   //更新插入结点的前驱指针域cur->next=p;    //更新前驱结点的后继指针域DL->prior=p;   //头结点的前驱指针cur=p; //更新L指针}
}

本题思路:

思路:遍历一遍双向循环链表，将偶数列拿出来，采用头插法建立一个新的链，最后再拼接起来。

本题代码，千万别忘了双向循环链表该考虑的都要考虑到

给出测试版代码和简化版代码

测试版代码

void reverse_doublecycleLink(DuLinkList &DL)
{//设置一个偶数表头(循环双链表)DuLinkList el=NULL;el=(DuLinkNode*)malloc(sizeof(DuLinkNode));el->next=el;el->prior=el;// 遍历一遍循环双链表DuLinkNode *p=DL->next; //定义一个指针控制循环DuLinkNode *pre=DL; //定义一个指针控制循环int jiou=0; //奇偶开头while(p!=DL)  //循环一遍{DuLinkNode *last=p->next;if(jiou==0)jiou=1;else jiou=0;  //奇偶标志if(jiou==0)  //偶数操作，{//将当前偶数头插进入el表p->next=el->next;el->next->prior=p;el->next=p;p->prior=el;//在原表中删掉这个偶数结点，删除结点时前趋后继都要修改pre->next=last;last->prior=pre;p=last;  //pre此时不变}else{p=p->next;pre=pre->next;}}//检验一下，当前DL的打印p=DL->next;while(p!=DL){printf("%d->",p->data);p=p->next;}printf("\n");//检验一下，当前el的打印p=el->next;while(p!=el){printf("%d->",p->data);p=p->next;}printf("\n");//检验成功，进行合并操作，需要el的尾指针和pl的尾指针,因为是循环链表直接能拿到
//    DuLinkNode *tail_dl=DL;
//    DuLinkNode *tail_el=el;
//    while(tail_dl->next!=DL)
//    {
//        tail_dl=tail_dl->next;
//    }
//    while(tail_el->next!=el)
//    {
//        tail_el=tail_el->next;
//    }
//    printf("el的尾指针%d\n",el->prior->data);printf("连接前的DL某尾的后继是%d\n",DL->prior->next->data);DL->prior->next=el->next;printf("连接后的DL某尾的后继是%d\n",DL->prior->next->data);el->next->prior=DL->prior;  //屁股连好了el->prior->next=DL;DL->prior=el->prior;  //头也连接好了// 终极检测//检验一下，当前DL的打印p=DL->next;while(p!=DL){printf("%d->",p->data);p=p->next;}printf("\n");}

简化版代码

void reverse_doublecycleLink(DuLinkList &DL)
{//设置一个偶数表头(循环双链表)DuLinkList el=NULL;el=(DuLinkNode*)malloc(sizeof(DuLinkNode));el->next=el;el->prior=el;// 遍历一遍循环双链表DuLinkNode *p=DL->next; //定义一个指针控制循环DuLinkNode *pre=DL; //定义一个指针控制循环int jiou=0; //奇偶开头while(p!=DL)  //循环一遍{DuLinkNode *last=p->next;if(jiou==0)jiou=1;else jiou=0;  //奇偶标志if(jiou==0)  //偶数操作，{//将当前偶数头插进入el表p->next=el->next;el->next->prior=p;el->next=p;p->prior=el;//在原表中删掉这个偶数结点，删除结点时前趋后继都要修改pre->next=last;last->prior=pre;p=last;  //pre此时不变}else{p=p->next;pre=pre->next;}}DL->prior->next=el->next;el->next->prior=DL->prior;  //屁股连好了el->prior->next=DL;DL->prior=el->prior;  //头也连接好了}