无锡网站策划_今日楼市新闻头条_网站搭建费用_百度搜索风云榜

一、前言

哦了兄弟们，咱们上次在详解链表OJ题的时候，有一部分OJ题呢up并没有整理完，这一个星期呢，up也是在不断的学习并且沉淀着，也是终于把剩下的题给整理完毕了，现在继续分享给大家。

二、OJ续享

2.1相交链表

力扣160 相交链表链接

首先咱们先来判断什么样的链表才是相交链表：
画图展示：

那么在判断完毕之后，我们又该如何实现呢?(解题思路请看图中文字)

代码展示：

typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {ListNode* pa = headA;ListNode* pb = headB;int sizeA = 0;int sizeB = 0;while(pa){sizeA++;//计算A链表的节点个数pa = pa->next;}while(pb){sizeB++;//计算B链表的结点个数pb = pb->next;}int gap = abs(sizeA-sizeB);//计算差值ListNode* shorth = headA;ListNode* longth = headB;if(sizeA>sizeB)//确定到底谁是长链表，谁是短链表{longth = headA;shorth = headB;}while(gap--){longth = longth->next;//让长链表先走gap步}while(longth)//遍历找寻两个链表是否有相同结点{if(longth==shorth){return longth;}shorth = shorth->next;longth = longth->next;}return NULL;
}

2.2环形链表1

力扣141 环形链表1链接

咱们还是先来判断怎样才是一个环形链表：
画图展示（解题思路请看图中文字）：

代码展示：

 typedef struct ListNode ListNode;//快慢指针
bool hasCycle(struct ListNode *head) {ListNode* slow = head;ListNode* fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;if(slow == fast){return true;}}return false;
}

2.2环形链表2

力扣142 环形链表2链接

刚刚我们实现了如何判断环形链表，那我们现在再来升级一下难度，在判断完是环形链表之后，再返回这个环开始的第一个结点。那么又具体怎么实现呢
画图展示（解题思路请看图中文字）：

代码展示：

 typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head) {ListNode* slow = head;ListNode* fast = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;if (slow == fast){ListNode* pcur = head;while (pcur != slow){pcur = pcur->next;slow = slow->next;}return pcur;}}return NULL;
}

三、总结

到这里，数据结构——链表的一些基础的经典OJ题up就给大家全部分析完毕了。可能有一些宝子会比较疑惑——关于环形链表，快慢指针不是用来找链表的中间结点的吗？为什么这里也同样适用呢？我只能说，这个问题问得太好了。但是up这次先不给大家证明，我先把这个问题留给大家，宝子们可以开动你们的灵活小脑袋想想，后续up会专门出一期关于数学证明环形指针的内容(如果你们已经证明出来了，可以给我留言看咱们的思路是否相同)，大家敬请期待哦。最后，希望大家可以一键三连，谢谢大家！

每一次挥汗如雨，都是通往成功路上的坚实步伐。