顺序表，链表，复杂度相关的OJ题

• 点击表格内对应链接跳转对应内容⬇️⬇️⬇️

1 消失的数字

• 链接：消失的数字

• 思路解析：第一种思路，因为异或运算中，只要和自己异或就是0，和0异或依然是本身，而我们知道数组中的数字是0到n，所以我们可以让缺少数字的数组中所有的数字和原本所有的数字都异或一遍，相同的数字异或以后都变成零了，最后得到的数字就是那个缺失的数字，因为这个数字缺失了，无法和相同的自己异或成0，第二种思路,把原本该有的数字都累加在一起，减去缺少数字的数组中所有的数字，最后得到的就是那个缺失的数字。

• 第一种思路：

intmissingNumber(int*nums,intnumsSize){intx=0;for(inti=0;i<numsSize;i++){x^=nums[i];}for(inti=0;i<=numsSize;i++){x^=i;}returnx;}

• 代码解析：创建整型变量x，第一个for循环中让x把缺少数字数组中的所有数字都异或一遍，然后在第二个for循环中把原本所有的数字都异或一遍，最后所有出现两次的数字都异或成0了，只有缺少的那个数字只出现了一次，所以最后异或的结果就是缺少的那个数字

• 第二种思路：

intmissingNumber(int*nums,intnumsSize){intsum=0;for(inti=0;i<=numsSize;i++){sum+=i;}for(inti=0;i<numsSize;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部分进行反转，最后整体反转reverse（A + B）,也就等于 reverse(B) + reverse(A),但是B和A都已经反转过了，所以最后就是B正序+A正序

• 代码演示：⬇️

voidreverse(int*nums,intleft,intright){while(left<right){inttmp=nums[left];nums[left]=nums[right];nums[right]=tmp;left++;right--;}}voidrotate(int*nums,intnumsSize,intk){k=k%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(head==NULL){returnhead;}n1=NULL;n2=head;n3=head->next;while(n2){//改变n2的指向n2->next=n1;//移动三个指针变量n1=n2;n2=n3;if(n3){n3=n3->next;}}returnn1;}//查找链表的中间节点structListNode*middleNode(structListNode*head){ListNode*fast,*slow;fast=slow=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;}returnslow;}//判断回文class PalindromeList{public:boolchkPalindrome(ListNode*A){ListNode*mid=middleNode(A);ListNode*reverse=reverseList(mid);while(A&&reverse){if(A->val!=reverse->val)returnfalse;A=A->next;reverse=reverse->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*pcur=headA;intcount1=0;intcount2=0;while(pcur){count1++;pcur=pcur->next;}pcur=headB;while(pcur){count2++;pcur=pcur->next;}if(count1>count2){count1-=count2;while(count1--){headA=headA->next;}while(headA&&headB){if(headA==headB){returnheadA;}headA=headA->next;headB=headB->next;}}else{count2-=count1;while(count2--){headB=headB->next;}while(headA&&headB){if(headA==headB){returnheadA;}headA=headA->next;headB=headB->next;}}returnNULL;}

• 代码解析将两个头节点分别赋给pcur,遍历原链表得到两个链表的长度count1和count2,if语句比较count1和count2的长短，让大的count减去短的得到差值，然后让长的链表走到差值位置，使两条链表的长度相同，然后在headA 和 headB 不为NULL 的条件下进入while循环，如果headA 和 headB出现相同的地址则代表是相交链表，return 的就是相交的节点，如果headA 和 headB 不相同则一直往下一个节点走，如果始终没出现相同节点，则最后返回NULL

5 链表中倒数第K个节点

• 链接：链表中倒数第K个节点

• 思路解析：输出倒数第K个节点，倒数第K个节点中，节点到NULL的距离是K 个节点，而快慢指针中，我们可以控制快指针和慢指针的距离为K，然后快慢指针同时走相同的距离，当快指针到NULL时，慢指针和快指针的距离为K，也就是慢指针到NULL的距离为K，这时候慢指针所在的节点就是倒数第K个节点

typedefstructListNodeListNode;structListNode*FindKthToTail(structListNode*pListHead,intk){ListNode*slow=pListHead;ListNode*fast=pListHead;while(k--){if(fast==NULL){returnNULL;}fast=fast->next;}while(slow&&fast){slow=slow->next;fast=fast->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的距离就是K，slow就是倒数第k个节点。

6 环形链表

• 链接：环形链表

• 思路解析：大多数的思路是：遍历链表的时候，一个节点的地址出现了两次，说明链表中有两个节点的next指向的是这个出现两次的节点，而出现两次的节点就代表这个链表是环链表，但是成环的链表是没有尽头的，无法通过遍历每个节点，来得出是否存在相同节点，因为如果匹配的这一个节点不是环节点，遍历的指针进入环中之后会一直遍历，没有停止的条件，因为环中一直有节点给这个遍历指针遍历。所以遍历的思路是不行的，我们可以使用快慢指针的思路，快指针比慢指针先入环，等到慢指针入环以后，因为快指针的速度比慢指针快，所以在环中，快指针是可以追上慢指针的，一旦快指针遇到了慢指针，则说明这个链表是带环链表

typedefstructListNodeListNode;boolhasCycle(structListNode*head){ListNode*slow=head;ListNode*fast=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;if(fast==slow){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*slow=head;ListNode*fast=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;if(fast==slow){returnfast;}}returnNULL;}structListNode*detectCycle(structListNode*head){ListNode*meet=hasCycle(head);if(meet==NULL){returnNULL;}while(meet!=head){meet=meet->next;head=head->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*pcur=head;Node*newnode=NULL;if(head==NULL){returnNULL;}//循环在原链表后面创建新的相同节点while(pcur){newnode=(Node*)malloc(sizeof(Node));newnode->next=pcur->next;pcur->next=newnode;newnode->val=pcur->val;pcur=pcur->next->next;}pcur=head;//newnode的random赋值while(pcur){if(pcur->random!=NULL){pcur->next->random=pcur->random->next;}else{pcur->next->random=pcur->random;}pcur=pcur->next->next;}//把新链表和原链表分离pcur=head;Node*newhead=head->next;Node*newpcur=newhead;while(pcur){pcur->next=newpcur->next;pcur=pcur->next;if(pcur!=NULL){newpcur->next=pcur->next;newpcur=newpcur->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是非法的。
  

• 点击表格内对应链接跳转对应内容⬇️⬇️⬇️