电子商务与网站建设的报告,个人主页简介,东莞公司品牌网站建设,电子商务网站建设的基本过程单链表OJ题 前言一、返回链表开始入环的第一个节点思路一思路二 二、返回链表的深度拷贝总结 前言
此次练习题有两道#xff01; 有点小难度#xff0c;但相信难不住大家的#xff01; 我也会给出两道OJ题的链接#xff0c;大家也赶快去试一试吧 一、返回链表开始入环的第… 单链表OJ题 前言一、返回链表开始入环的第一个节点思路一思路二 二、返回链表的深度拷贝总结 前言
此次练习题有两道 有点小难度但相信难不住大家的 我也会给出两道OJ题的链接大家也赶快去试一试吧 一、返回链表开始入环的第一个节点
题目链接OJ链接 提示 链表中节点的数目范围在范围 [0, 104] 内 -105 Node.val 105 pos 的值为 -1 或者链表中的一个有效索引 本题有两个解析思路~
思路一 代码演示
//解题方法一
struct ListNode *detectCycle(struct ListNode *head) {struct ListNode *move1head;struct ListNode *move2head;while(move1move2move2-next){//快慢指针移动move1move1-next;move2move2-next-next;if(move1move2){{//找到相遇点struct ListNode *meetmove1;//meet从相遇点开始移动struct ListNode *move3head;//move3从head开始移动while(meet!move3){//两个指针同时移动找到起始点meetmeet-next;move3move3-next;}return meet;}}return NULL;
}思路二 提示如果不了解如何找出公共点的的话前面的博客会对大家有所帮助 博客链接单链表OJ题 代码演示
//解题方法二
struct ListNode *detectCycle(struct ListNode *head) {struct ListNode *move1head;struct ListNode *move2head;while(move1move2move2-next){//快慢指针移动move1move1-next;move2move2-next-next;if(move1move2){//找到相遇点struct ListNode *tempmove1;//保存相遇点位置move1move1-next;//将move1变为第二链表起始点temp-nextNULL;//将相遇点的next置空struct ListNode *head1head;struct ListNode *head2move1;int len10,len20;while(head1!NULL){//计算链表长度len1;head1head1-next;}while(head2!NULL){head2head2-next;len2;}int kabs(len1-len2);//得到两链表长度相减的绝对值//将longs指向较长的链表shorts指向较短的链表struct ListNode *shortshead;struct ListNode *longsmove1;if(len1len2){shortsmove1;longshead;}while(k--longs!NULL){//较长的链表移动k位longslongs-next;}if(k0longsNULL){return NULL;}while(shorts!longs){//两链表同时遍历找到第一个公共点shortsshorts-next;longslongs-next;}return longs;}}return NULL;
}二、返回链表的深度拷贝
题目链接OJ链接 提示 0 n 1000 -104 Node.val 104 Node.random 为 null 或指向链表中的节点。 解题思路
代码演示
struct Node* BuyNewnode(int x){//创建结点函数struct Node*newnode(struct Node*)malloc(sizeof(struct Node));newnode-valx;newnode-nextNULL;newnode-randomNULL;return newnode;
}
//查找random所在位置的函数
struct Node* findrandom(struct Node* head,struct Node* newhead,struct Node* random){struct Node*move1head;struct Node*move2newhead;while(move1!random){move1move1-next;move2move2-next;}return move2;
}struct Node* copyRandomList(struct Node* head) {struct Node*movehead;struct Node*newheadNULL;struct Node*tailNULL;while(move!NULL){//将新建结点依次尾插到新链表中if(tailNULL){struct Node*newnode BuyNewnode(move-val);newheadtailnewnode;movemove-next;}else{struct Node*newnode BuyNewnode(move-val);tail-nextnewnode;tailtail-next;movemove-next;}}struct Node*setrannewhead;struct Node*findranhead;while(setranfindran){struct Node*tempfindrandom(head,newhead,findran-random);setran-randomtemp;setransetran-next;findranfindran-next;}return newhead;
}总结
这次的题目稍稍有些难度 但是绝对难不倒大家的 加油 加油
