ios移动网站开发工具,手机网站开发样板,wordpress 博主认证,学建筑的网站目录
1.环形链表Ⅰ
编辑
思路 #xff1a;
思路拓展
问题一#xff1a;
问题二#xff1a;
总结#xff1a;
问题三#xff1a;
证明总结第三点 总结#xff1a;
2. 环形链表Ⅱ
思路一
思路二
3.相交链表 思路#xff1a; 1.环形链表Ⅰ
141. 环形链…
目录
1.环形链表Ⅰ
编辑
思路
思路拓展
问题一
问题二
总结
问题三
证明总结第三点 总结
2. 环形链表Ⅱ
思路一
思路二
3.相交链表 思路 1.环形链表Ⅰ
141. 环形链表 - 力扣LeetCode 给你一个链表的头节点 head 判断链表中是否有环。 如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。注意pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。 如果链表中存在环 则返回 true 。 否则返回 false 。 思路 我们考虑环状时如果是简单的循环next来判定只会进入死循环 需要引入新思维判断是否带环可以想象操场追赶问题两个人在操场跑让一个人先进场跑再让另外一名选手进场如果环足够大如何让后入场的选手追赶上前面的答案是后来者加快速度。 而在这道题中我们用快慢指针概念一个指针走两步一个走一步进入环后快指针一定会和慢指针相遇 为什么一定会相遇呢 距离为N每次快指针走两步慢指针走一步相当于距离每次减少1 如此距离缩短肯定会相遇而当快慢指针相遇的时候就是证明该链表带环 而如果不带环快指针将链表走完后表明退出了循环即可 bool hasCycle(struct ListNode *head) {//快慢指针struct ListNode* slow head;struct ListNode* fast head;while(fast fast-next){fast fast-next-next;slow slow-next;if(fast slow){return true;}}return false;
}
思路拓展 上面说到距离缩小1一定会追上那如果距离一次缩小2呢是不是更快的会相遇呢 如果一次距离缩小n是不是更快呢如此延申我们可以发现有三个拓展 1. slow一次走一步fast一次走两步一定会相遇吗 2.slow一次走一步fast一次走三步一定会相遇吗 3.slow一次走n步fast一次走m步一定会相遇吗 mn1 问题一 距离缩小为1的话一定会遇上我们上面证明了 问题二 当slow进环时fast和它的距离为N一次减少2。分为两种情况 1.当N是偶数时 2.当N是奇数时 所以我们可以发现当N是偶数时依然可以追上 当N是奇数是得到下一轮 这时候要看 C-1是奇偶数 如果c-1是偶数在下一轮就会追上 如果c-是奇数则会开始无限循环下去一直追击不上 总结 1.如果N是偶数第一轮内就会追上 2.如果N是奇数C是奇数第一轮会错过下一轮会追击C是奇数C-1就会是偶数 3.如果N是奇数C是偶数就永远追不上 问题三 这个类似问题二每次距离缩小是m-n(1); 如果N%(m-n) 0 说明一圈就可以追上 如果是-1则是C-1-2就是C-2 如果这个数是m-n的倍数如果不是倍数则可能存在死循环 证明总结第三点 写到这里时问题二的 总结第三点是否真的成立呢 3.如果N是奇数C是偶数就永远追不上 此刻slow走了L的路程fast走了 L nC - N 在这时可以推论出公式 推论出来的这个公式 2L一定是偶数 n*C:总结第三点假设这里是偶数 N如果要满足此公式N就不可能会奇数 所以 3.如果N是奇数C是偶数就永远追不上 这句话的条件不成立 总结 1.如果N是偶数第一轮内就会追上 2.如果N是奇数C是奇数第一轮会错过下一轮会追击C是奇数C-1就会是偶数 只存在这两种 bool hasCycle(struct ListNode *head) {//快慢指针struct ListNode* slow head;struct ListNode* fast head;while(fast fast-next){fast fast-next-next;slow slow-next;if(fast slow){return true;}}return false;
} 在这种情况下该情况其实还可以推论出另一个公式结论 。这就是第二题 2. 环形链表Ⅱ 142. 环形链表 II - 力扣LeetCode 给定一个链表的头节点 head 返回链表开始入环的第一个节点。 如果链表无环则返回 null。 如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。如果 pos 是 -1则在该链表中没有环。注意pos 不作为参数进行传递仅仅是为了标识链表的实际情况。 不允许修改 链表。 思路一 我们依旧用上一道题的画图思路来解决 第一步先判断是否存在环 第二部找到入口点 用快慢指针方法slow走一步fast走两步 struct ListNode *detectCycle(struct ListNode *head) {//快慢指针struct ListNode* slow head;struct ListNode* fast head;while(fast fast-next){fast fast-next-next;slow slow-next;if(fast slow) //相遇了{struct ListNode* meet slow;while(head ! meet) //起点和相遇点{head head-next;meet meet-next;}//找到入口点了return meet;}}return false;
}
思路二 这道题还有另外一种解法就是在相遇点meet这里将下一个节设为newnode再将meet-next置NULL这样就将带环链表问题转换成 相交链表问题 而这种解法自然有相交链表的题 但是这种解法比较复杂建议用思路一的 3.相交链表
160. 相交链表 - 力扣LeetCode 给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回 null 。 题目数据 保证 整个链式结构中不存在环。 注意函数返回结果后链表必须 保持其原始结构 。 思路 题目两种情况存在相交和不相交 相交还有前后长短问题 1.先判断是否有相交点如果相交尾节点一定相同 2.计算两条链表的长度让长链表先走差距步这样可以让两条链表处于相同head 3.再让两条链接一起走直到遇到相同点 返回相遇点或者是结束链表遍历返回NULL struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode* curA headA,*curB headB;//计算两条链表长度int lenA 0;int lenB 0;while(curA){lenA;curA curA-next;}while(curB){lenB;curB curB-next;}//算出长度差int n abs(lenA-lenB);//假设lenA 长于lenBstruct ListNode* longlist headA,*shortlist headB;if(lenBlenA) //假设不成立交换{longlist headB;shortlist headA;}//长的先走差值while(n--){longlist longlist-next;}//判断是否相等while(longlist ! shortlist){longlist longlist-next;shortlist shortlist-next; }//到这里要么相等要么链表不相交已经走完了是NULLreturn longlist;
}
