电脑网站大全网站多长时间到期

当前位置： 首页 > news >正文

电脑网站大全,网站多长时间到期,wordpress下边音乐,管家婆免费资料网站160. 相交链表 给你两个单链表的头节点 headA 和 headB #xff0c;请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点#xff0c;返回 null 。 AC写法一 struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {//思…160. 相交链表 给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回 null 。 AC写法一 struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode headB) {//思路基本一样struct ListNode curA headA;struct ListNode* curB headB;int lenA 0,lenB 0;//先计算两个的长度while(curA){curA curA-next;lenA;}while(curB){curB curB-next;lenB;}//遍历结束后回到头结点curA headA;curB headB;//计算差距并开始走差距步,diff大小可以知道哪一个更长int diff lenA - lenB;if(diff 0) {while(diff 0) {curA curA-next;diff–;}} else if(diff 0) {while(diff 0) {curB curB-next;diff;}}//当两个不相等就继续走但是要注意任意一个都不能为空while(curA curB curA ! curB){curA curA-next;curB curB-next;}//如果没有相交两个也都走到了空//如果相交了此刻停留的位置也正好是相交初始节点直接返回return curA; } AC写法二 struct ListNode* curA headA;struct ListNode* curB headB;int lenA 0,lenB 0;//lenA和lenB最后计数都会少了一个//但这道题目的是为了计算差值//同时都少一个不会对结果有影响while(curA-next){curA curA-next;lenA;}while(curB-next){curB curB-next;lenB;}//如果尾节点不相同就没有相交。直接返回if(curA ! curB){return NULL;}//abs函数计算绝对值int n abs(lenA - lenB);struct ListNode* longList headA, *shortList headB;//上一步做了假设如果假设不成立那就交换后边就不用关心长的是哪条链表了if(lenB lenA){longList headB;shortList headA;}//长的先走差距步while(n–){longList longList-next;}while(longList ! shortList){longList longList-next;shortList shortList-next;return longList; 代码思路 上述两种代码的基本思路是一样的具体细微的差别已经标注在代码中接下来进行陈述 首先看题寻找相交节点那么这个链表不可能是 X 型因为节点只能存储一个节点地址所以只能是 Y 型或者不想交是平行这一点看题目就可以明白。 最容易想到的暴力法双指针一个指向链表A一个指向链表BlenA进行链表A的遍历将每一个节点与lenB当前所指的节点进行比较看是否相等都不相等则lenB指向下一个LenA再进行比较这样的方法时间复杂度为O(N^2) 还有一种时间复杂度为O(N)的方法。观察 Y 型结构假设有两个指针指向两条链表的开始同时开始走并进行比较由于链表相交前长度可能不一样不一样的时候两个指针不可能相遇但如果要两个指针相遇相交之前有部分必须对应那现在就是解决如何使两个指针按照我们需要的对应起来了当较长的链表先走走到剩余部分和较短链表一样时两个指针一起走就解决了这个问题而这部分先走的就是两条链表的长度差所以两个指针都遍历一遍链表得出各自长度遍历的同时可以比较尾节点是否相同不相同直接说明没有相交然后相减得出长度差就可以实现如有交点两个指针一定会相遇的情况了。

1. 环形链表 给你一个链表的头节点 head 判断链表中是否有环。 如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。注意pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。 如果链表中存在环 则返回 true 。 否则返回 false 。 AC bool hasCycle(struct ListNode head) {struct ListNode slow head, * fast head;while(fast fast-next){slow slow-next;fast fast-next-next;if(slow fast){return true;}}return false; } 代码思路 快慢指针绝绝绝绝绝绝 环形链表难点在于不知道哪里开始的环但是在环里就没有前后之分使用快慢指针从头开始走fast走两步slow走一步当fast走进环的时候slow一定还在后边但是当slow也进环以后由于两者速度不一样fast会追上slow想象一下速滑运动中的套圈而在环中的话就一定会相遇。如果没有环那么fast会指向空。只要思路正确并不难写。至于为什么while循环中还需要fast-next也不能为空因为fast一次走两步当fast指向尾节点的时候没有fast-next-next. 为什么快指针每次走两步慢指针走一步可以 假设链表带环两个指针最后都会进入环快指针先进环慢指针后进环。当慢指针刚 进环时可能就和快指针相遇了最差情况下两个指针之间的距离刚好就是环的长度。 此时两个指针每移动一次之间的距离就缩小一步不会出现每次刚好是套圈的情 况因此在满指针走到一圈之前快指针肯定是可以追上慢指针的即相遇。 快指针一次走3步走4步…n步行吗 142. 环形链表 II 给定一个链表的头节点 head 返回链表开始入环的第一个节点。 如果链表无环则返回 null。 如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。如果 pos 是 -1则在该链表中没有环。注意pos 不作为参数进行传递仅仅是为了标识链表的实际情况。 不允许修改 链表。 AC struct ListNode *detectCycle(struct ListNode head) {struct ListNode slow head, fast head;while(fast fast-next){slow slow-next;fast fast-next-next;if(slow fast){struct ListNode meet slow;while(head ! meet){head head-next;meet meet-next;}return meet;}}return NULL; } 代码思路 说明 H为链表的起始点E为环入口点M与判环时候相遇点 设 环的长度为R,H到E的距离为L E到M的距离为X 则M到E的距离为R-X 在判环时快慢指针相遇时所走的路径长度 fastLX nR slowL X 注意 1.当慢指针进入环时快指针可能已经在环中绕了n圈了n至少为1 因为快指针先进环走到M的位置最后又在M的位置与慢指针相遇 2.慢指针进环之后快指针肯定会在慢指针走一圈之内追上慢指针 因为慢指针进环后快慢指针之间的距离最多就是环的长度而两个指针在移动时每次它们至今的距离都缩减一步因此在慢指针移动一圈之前快指针肯定是可以追上慢指针的 而快指针速度是满指针的两倍因此有如下关系是 2 * (L X)L X nR LX nR L nR - X (n为1,2,3,4..n的大小取决于环的大小环越小n越大) 极端情况下假设 n1,此时L R -X 即一个指针从链表起始位置运行一个指针从相遇点位置绕环每次都走一步两个指针最终会在入口点的位置相遇 思路二将meet的下一个节点meet-next交给一个新指针newhead然后将meet的next置空meet-next NULL此刻就将题转化为了链表相交问题但是这种写代码更为复杂此处不做尝试