点击表格内对应链接跳转对应内容⬇️⬇️⬇️作者主页吃透C语言专栏数据结构Gitee仓库文章目录1 消失的数字2 轮转数组3 链表的回文结构4 相交链表5 链表中倒数第K个节点6 环形链表7 环形链表 ||8 随机链表的复制1 消失的数字链接消失的数字思路解析第一种思路因为异或运算中只要和自己异或就是0和0异或依然是本身而我们知道数组中的数字是0到n所以我们可以让缺少数字的数组中所有的数字和原本所有的数字都异或一遍相同的数字异或以后都变成零了最后得到的数字就是那个缺失的数字因为这个数字缺失了无法和相同的自己异或成0第二种思路,把原本该有的数字都累加在一起减去缺少数字的数组中所有的数字最后得到的就是那个缺失的数字。第一种思路intmissingNumber(int*nums,intnumsSize){intx0;for(inti0;inumsSize;i){x^nums[i];}for(inti0;inumsSize;i){x^i;}returnx;}代码解析创建整型变量x第一个for循环中让x把缺少数字数组中的所有数字都异或一遍然后在第二个for循环中把原本所有的数字都异或一遍最后所有出现两次的数字都异或成0了只有缺少的那个数字只出现了一次所以最后异或的结果就是缺少的那个数字第二种思路intmissingNumber(int*nums,intnumsSize){intsum0;for(inti0;inumsSize;i){sumi;}for(inti0;inumsSize;i){sum-nums[i];}returnsum;}代码解析第一个for循环中把原本所有的数字累加在一起放在sum中第二个for循环中用sum依次减去数组中所有的数字最后剩下的数字就是数组中没有的数字也就是缺失的数字2 轮转数组链接轮转数组思路解析三步反转reverse(reverse(A)) A ,对一个数组连续反转结果不变reverse(A B) reverse(B) reverse(A),反转的意思是数组中对称位置的元素交换比如1234中1和4进行交换2和3进行交换三步反转步骤先对A部分进行反转再对B部分进行反转最后整体反转reverseA B,也就等于 reverse(B) reverse(A),但是B和A都已经反转过了所以最后就是B正序A正序代码演示⬇️voidreverse(int*nums,intleft,intright){while(leftright){inttmpnums[left];nums[left]nums[right];nums[right]tmp;left;right--;}}voidrotate(int*nums,intnumsSize,intk){kk%numsSize;//先k部分反转reverse(nums,numsSize-k,numsSize-1);//再除了k部分反转reverse(nums,0,numsSize-k-1);//最后整体反转reverse(nums,0,numsSize-1);}代码解析⬆️重点1 写好reverse反转函数 2 k%numsSize 3 找对需要反转位置的下标 1 reverse函数设置left 和 right 下标在right 下标 大于 left 下标的情况下进入循环把right下标处的元素和left下标处的元素交换然后left往后移right–往左移2 当数组中的元素轮转的次数等于自身元素个数的时候相当于没轮转所以要用k%numsSize ,%运算符求的是余数k是要轮转的元素个数k%numsSize是统计k中减去numsSize的个数以外还剩下几所以余数就是要实际要轮转的元素个数最后调用reverse函数时要反转的函数的下标要捋清楚3 链表的回文结构链接链表的回文结构思路解析我们学过1 找链表中间节点 2 反转链表 这样的话就可以找出中间节点把中间节点作为起点开始反转链表最后比较未反转的链表 和 反转的链表如果相等则链表为回文链表typedefstructListNodeListNode;//反转链表structListNode*reverseList(structListNode*head){ListNode*n1,*n2,*n3;if(headNULL){returnhead;}n1NULL;n2head;n3head-next;while(n2){//改变n2的指向n2-nextn1;//移动三个指针变量n1n2;n2n3;if(n3){n3n3-next;}}returnn1;}//查找链表的中间节点structListNode*middleNode(structListNode*head){ListNode*fast,*slow;fastslowhead;while(fastfast-next){fastfast-next-next;slowslow-next;}returnslow;}//判断回文class PalindromeList{public:boolchkPalindrome(ListNode*A){ListNode*midmiddleNode(A);ListNode*reversereverseList(mid);while(Areverse){if(A-val!reverse-val)returnfalse;AA-next;reversereverse-next;}returntrue;}};代码解析调用middleNode函数找出中间节点再调用reverseList函数反转中间节点作为起点的链表最后让前段链表和后段链表中的节点进行逐个匹配while的循环条件就是两个链表其中一个为NULL就停下来循环体中判断A -val 和 reverse -val,是否相等如果不相等直接返回false,节点相等则两个链表同时往下一个节点走继续匹配最后走到NULL跳出while循环return true。其中while(A reverse)是可以省略A 直接写while(reverse),因为reverse永远比A先走到NULL偶数节点数链表 1-2-2-1中A链表为1-2-2-NULL,反转链表为1-2-NULL,反转的本质就是把第二个2的next置为NULL但是前一个2依然连着第二个2没有改变第一个2的next,这就很好解释奇数节点链表了1-2-3-2-1,A链表为1-2-3-NULL,反转链表为1-2-3-NULL,同时走到NULL反转函数最后改变的节点依然是3-NULL,也就是3的next指向NULL所以A链表中的2依然链接3所以才能完整比较两个链表4 相交链表链接相交链表思路解析两个链表相交的话共同点是相交的节点地址是相同的两条链表节点中的val可以是任何数值所以不能通过判断两条链表节点中的val值是否相等来判断节点。所以通过节点地址判断的话有两种方法方法1 是让其中一个链表中的每一个节点都遍历匹配另一个链表中的每一个节点时间复杂度为O(n^2),方法2 是分别遍历两条链表得到各自的长度相减得到两个链表的长度差让长链表的头节点走长度差的距离使两条链表的长度相等然后同时遍历匹配两个链表如果两条链表有相交则同长度的前提下相同节点的位置出现在每个链表中的位置是相同的typedefstructListNodeListNode;structListNode*getIntersectionNode(structListNode*headA,structListNode*headB){ListNode*pcurheadA;intcount10;intcount20;while(pcur){count1;pcurpcur-next;}pcurheadB;while(pcur){count2;pcurpcur-next;}if(count1count2){count1-count2;while(count1--){headAheadA-next;}while(headAheadB){if(headAheadB){returnheadA;}headAheadA-next;headBheadB-next;}}else{count2-count1;while(count2--){headBheadB-next;}while(headAheadB){if(headAheadB){returnheadA;}headAheadA-next;headBheadB-next;}}returnNULL;}代码解析将两个头节点分别赋给pcur,遍历原链表得到两个链表的长度count1和count2,if语句比较count1和count2的长短让大的count减去短的得到差值然后让长的链表走到差值位置使两条链表的长度相同然后在headA 和 headB 不为NULL 的条件下进入while循环如果headA 和 headB出现相同的地址则代表是相交链表return 的就是相交的节点如果headA 和 headB 不相同则一直往下一个节点走如果始终没出现相同节点则最后返回NULL5 链表中倒数第K个节点链接链表中倒数第K个节点思路解析输出倒数第K个节点倒数第K个节点中节点到NULL的距离是K 个节点而快慢指针中我们可以控制快指针和慢指针的距离为K然后快慢指针同时走相同的距离当快指针到NULL时慢指针和快指针的距离为K也就是慢指针到NULL的距离为K这时候慢指针所在的节点就是倒数第K个节点typedefstructListNodeListNode;structListNode*FindKthToTail(structListNode*pListHead,intk){ListNode*slowpListHead;ListNode*fastpListHead;while(k--){if(fastNULL){returnNULL;}fastfast-next;}while(slowfast){slowslow-next;fastfast-next;}returnslow;}代码解析设置快慢指针slow和fast都指向头节点while循环中让fast先走K个节点这样fast距离头节点的距离就是K也就是fast距离slow节点距离就是K但是需要注意的是k是可能大于链表节点个数的比如链表3个节点但是k是4也就是在3个节点的链表中找倒数第4个节点while的停止条件就是K 为 0但是K大于链表节点数所以即使fast走到NULL了依然会继续往后走NULL-next是非法的所以我们要设置一个if判断当fast为NULL的时候则说明链表要么为NULL要么K大于链表节点个数这时候直接返回NULL可以这样判断的前提条件是当fast起始点在NULL只有一种情况那就是K的大小是链表节点的大小这时候需要返回的就是第一个节点这时候fast走K步直接走到NULL直接跳过while循环返回slow这时候slow就是第一个节点而fast起点为NULL的时候k已经变成0了是不可能进入循环的不会去判断fast NULL,可能说的不清楚也就是说fast走到NULL以后k–已经变成0了不会再进入循环判断fast为NULL然后return NULL,正常走到NULL作为fast起点的时候是在if的后面发生所以不会触发if ,同时k 0不会进入循环触发if ,触发if的条件只有当fast 为NULL了但是k没为0依然要让fast继续往下走这时候就会触发if,所以正常情况下fast 走到NULL作为起点的时候k也同时为0这样就不会让fast为NULL还要往下走只有fast为NULL但是k不为0才会触发if不让fast往下走这种情况就说明原链表为NULL或者k大于链表节点个数最后fast走到NULL的时候slow到NULL的距离就是Kslow就是倒数第k个节点。6 环形链表链接环形链表思路解析大多数的思路是遍历链表的时候一个节点的地址出现了两次说明链表中有两个节点的next指向的是这个出现两次的节点而出现两次的节点就代表这个链表是环链表但是成环的链表是没有尽头的无法通过遍历每个节点来得出是否存在相同节点因为如果匹配的这一个节点不是环节点遍历的指针进入环中之后会一直遍历没有停止的条件因为环中一直有节点给这个遍历指针遍历。所以遍历的思路是不行的我们可以使用快慢指针的思路快指针比慢指针先入环等到慢指针入环以后因为快指针的速度比慢指针快所以在环中快指针是可以追上慢指针的一旦快指针遇到了慢指针则说明这个链表是带环链表typedefstructListNodeListNode;boolhasCycle(structListNode*head){ListNode*slowhead;ListNode*fasthead;while(fastfast-next){fastfast-next-next;slowslow-next;if(fastslow){returntrue;}}returnfalse;}代码解析创建快慢指针fast 和 slow如果不是环快指针一定比慢指针先停下来所以while循环中只需要去判断fast是否为NULL即可但是fast一次是走两步的所以如果链表节点个数偶数的情况下需要判断fast-next是否为NULL如果fast-next为NULL说明这个快指针走到尾节点了无法继续执行一次走两步的操作因为fast为NULL的时候NULL-next是非法的如果链表节点个数是奇数的情况下需要判断fast是否为NULL因为fast一次性走两步当fast走到NULL的时候就代表这个链表已经走完了无法执行一次性走两步的操作而且fast必须在fast-next 的前面因为如果当链表节点为偶数的时候执行了fast走到了尾节点这时候fast不为NULL但是fast-next为NULL可以停下来如果链表的节点为奇数的时候fast为NULL,语句发生短路就不会去判断fast-next是否为NULL依然可以停下来但是如果fast-next在fast的前面的话如果链表的节点为偶数的话当fast走到NULL的时候会去判断fast-next,这时候fast是为NULL 的所以判断NULL的next是非法的所以顺序不能乱。设置好while循环的判断条件以后确保在不为环链表的的情况下fast-next-next能在正确的位置停下来不会导致fast为NULL的时候或者fast-next为NULL的时候还继续执行fast-next-next的操作在while循环体走让fast和slow一直走由于fast走两步slow走一步所以他们之间的相对速度是1也就是如果slow进环以后fast正以一次while循环缩短一个节点的距离的速度接近slow所以只要是环链表fast一定会遇到slow的衍生问题fast如果一次走三步的话会和slow相遇吗如何计算入环的节点7 环形链表 ||链接环形链表 ||思路解析求出相遇点后相遇点和头节点同时走最后会在入环点相遇typedefstructListNodeListNode;ListNode*hasCycle(structListNode*head){ListNode*slowhead;ListNode*fasthead;while(fastfast-next){fastfast-next-next;slowslow-next;if(fastslow){returnfast;}}returnNULL;}structListNode*detectCycle(structListNode*head){ListNode*meethasCycle(head);if(meetNULL){returnNULL;}while(meet!head){meetmeet-next;headhead-next;}returnmeet;}代码解析调用之前写的判断环形链表的函数当slow fast 的时候就到了fast和slow的相遇点x,用meet接收x节点如果链表不是环形链表则返回NULL所以先判断meet是否为NULL如果为NULL则直接返回NULL在while循环中条件判断为meet 不等于 head,只有相遇才停下来最后相遇的时候meet和head都在入环点8 随机链表的复制链接随机链表的复制题目理解题目的意思是根据原链表中节点的内容拷贝一个新的链表新链表中的所有节点的数据域要保持和原链表一致指针域中除了next还有一个random指针变量randown指针中链接的节点是随机的比如第二个节点中random链接的可能是链表中任何一个节点而我们拷贝的链表中random链接的节点在本链表中对应的位置要和被拷贝的链表中random对应被拷贝的链表中的节点一样对应的位置也就是链表中第一个节点random链接的是第三个节点所以拷贝的链表中第一个节点的random链接的也要是第三个节点拷贝的链表和原链表的地址没有任何联系但是我们要做到对应位置的拷贝思路解析在原链表的每个节点的后面创建一个相同的节点链接起来这些节点就是新链表的节点新链表的random也就是原链表中对应位置的random的next节点因为新链表的每一个节点都在原链表中对应节点的后面所以random节点自然也在原链表中对应位置random的后面得到新链表中的random以后最后再把新链表从原链表取下来把原链表恢复即可typedefstructNodeNode;structNode*copyRandomList(structNode*head){Node*pcurhead;Node*newnodeNULL;if(headNULL){returnNULL;}//循环在原链表后面创建新的相同节点while(pcur){newnode(Node*)malloc(sizeof(Node));newnode-nextpcur-next;pcur-nextnewnode;newnode-valpcur-val;pcurpcur-next-next;}pcurhead;//newnode的random赋值while(pcur){if(pcur-random!NULL){pcur-next-randompcur-random-next;}else{pcur-next-randompcur-random;}pcurpcur-next-next;}//把新链表和原链表分离pcurhead;Node*newheadhead-next;Node*newpcurnewhead;while(pcur){pcur-nextnewpcur-next;pcurpcur-next;if(pcur!NULL){newpcur-nextpcur-next;newpcurnewpcur-next;}}returnnewhead;}代码解析分三步第一步循环在原链表后面创建新的相同节点在这之前要先判断是否链表为NULL如果链表为NULL则直接返回NULL第一步pcur作为遍历指针同时作为while循环的判断条件malloc一个个新节点插入原节点后面并把val拷贝插入以后记得pcur往后走第二步newnode的random赋值在创建好节点的前提下才能通过原节点找到新节点对应的random节点也就是pcur-next-random,新节点的random 等于 pcur-random-next(原节点random的next) ,新节点都在对应的原节点的后面所以新节点的random也在原节点random的后面。random的拷贝关键点在于新节点random链接好了以后新节点和原节点始终要同步对应的节点才能找到对应的random,我是直接用pcur表示新节点的所以pcur换了位置新节点自然就换了位置第三步把新链表和原链表分离pcur遍历分离原链表和新链表的基础是创建一个newhead,然后让newpcur去改变一个个新节点的next,同时pcur改变一个个原节点的next,然后pcur和newpucr都要往下面走改变每一个节点依然需要判断pcur是否为NULL如果pcur为NULL则说明已经走到NULL分离结束不需要分离了所以在while循环里面也要判断pcur是否为NULL因为是pcur先走到下一个节点再去链接新的节点但是如果这时候pcur已经为NULL了则pcur-next是非法的。点击表格内对应链接跳转对应内容⬇️⬇️⬇️作者主页吃透C语言专栏数据结构Gitee仓库