如何用ps做网站导航条,劳保用品 技术支持 东莞网站建设,宣传品牌网站建设,商丘seo外包目录
一#xff0c;与链表相关的题目#xff08;2#xff09;
1.输入两个链表#xff0c;找出它们的第一个公共节点
2.给定一个链表#xff0c;判断链表中是否有环
3.给定一个链表#xff0c;返回链表开始入环的第一个节点#xff0c;若无则返回null 一#xff0c;…目录
一与链表相关的题目2
1.输入两个链表找出它们的第一个公共节点
2.给定一个链表判断链表中是否有环
3.给定一个链表返回链表开始入环的第一个节点若无则返回null 一与链表相关的题目2
1.输入两个链表找出它们的第一个公共节点
下面是两个相交的链表 此时要找两个链表的相交节点非常简单
只需要将两个链表的头节点分别向后移
当head1 head2 时说明改节点是它们的相交节点 但当两个链表长度不一样的时候就会出现问题 遇到这种情况一般会先求出两个链表的长度len1与len2让长的那个链表走两链表的差值步len1-len2/len2 - len1 之后走相同步数直至相遇 代码示例
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if (headA null || headB null) {return null;}ListNode cur1 headA;ListNode cur2 headB;int count1 0;int count2 0;while (cur1.next ! null) {count1;cur1 cur1.next;}cur1 headA;while (cur2.next ! null) {count2;cur2 cur2.next;}cur2 headB;int dif 0;if (count1 count2) {dif count1 - count2;while (dif ! 0) {cur1 cur1.next;dif--;}} else {dif count2 - count1;while (dif ! 0) {cur2 cur2.next;dif--;}}while (cur1 ! cur2) {cur1 cur1.next;cur2 cur2.next;}if (cur1 cur2) {return cur1;} else {return null;}}}
2.给定一个链表判断链表中是否有环 【思路】 快慢指针即慢指针一次走一步快指针一次走两步两个指针从链表起始位置开始运行如果链表带环则一定会在环中相遇否则快指针率先走到链表的末尾。比如陪女朋友到操作跑步减肥。 public class Solution {public boolean hasCycle(ListNode head) {ListNode fast head;ListNode slow head;while (fast ! null fast.next ! null) {fast fast.next.next;slow slow.next;if (fast slow) {return true;}}return false;}} 为什么快指针每次走两步慢指针走一步可以 假设链表带环两个指针最后都会进入环快指针先进环慢指针后进环。当慢指针刚进环时可能就和快指针相遇了最差情况下两个指针之间的距离刚好就是环的长度。此时两个指针每移动一次之间的距离就缩小一步不会出现每次刚好是套圈的情况因此在慢指针走到一圈之前快指针肯定是可以追上慢指针的即相遇。 3.给定一个链表返回链表开始入环的第一个节点若无则返回null
上一题我们知道了怎么求一个链表是否有环而其实这一题也不难。基于上一题的基础上我们给出以下推导 通过以上过程我们推导出头节点距入口处x其实是等于快指针和慢指针相遇点到入口处的距离y的所有我们大可在这里再次令slow等于head让fast和slow以相同的速度往后走因为速度一样路程一样所有它们再次相遇的地方就一定是这个环的入口点 这里是当fast只比slow多走一圈的情况 而还存在的情况就是当环很小而head距入口处又非常远时fast就会为了等待x进入环而多走n圈 此时我们还可以根据上一题的思路就可以推导出以下公式 详解 可以发现slow到入口点的距离x其实是等于转的圈数减一乘以圈的周长再加上slow和fast的相遇点距入口点的距离y的并且我们上一题的推导结果也符合该条公式。 此时代码就可以基于上一题的代码进行修改并书写 public class Solution {public ListNode detectCycle(ListNode head) {ListNode fast head;ListNode slow head;while (fast ! null fast.next ! null) {fast fast.next.next;slow slow.next;if (fast slow) {slow head;while (slow ! fast) {slow slow.next;fast fast.next;}return fast;}}return null;}}
