当前位置: 首页> 文旅> 旅游 > 江门seo_建筑公司企业如何成功_百度直播_搜索风云榜

江门seo_建筑公司企业如何成功_百度直播_搜索风云榜

时间:2025/7/11 10:26:38来源:https://blog.csdn.net/m0_64265848/article/details/146920595 浏览次数:0次
江门seo_建筑公司企业如何成功_百度直播_搜索风云榜

目录

一、相交链表思路

1.1 经典思路

2.1 双指针思路

二、相关算法题目

三、总结


一、相交链表思路

1.1 经典思路

1.遍历两个链表,计算各自长度,算出长度差diff;

2.让较长的链表的指针先移动diff 步;

3.然后两个指针同时移动,直到找到相同的节点(相交点)或到达末尾(不相交);

2.1 双指针思路

双指针解法不需要计算长度

两个指针pA和pB分别遍历两个链表,当到达末尾时开始指向另一个链表的头部;如果两个链表相交,则它们会在相交点相遇;如果不相交,最终会同时到达null;

为什么这样可以找到相交点:

1.如果没有相交点:

  • pA和pB最终会同时走到null,因为 pA 遍历A+B,pB 遍历 B+A,长度相同;
  • 此时 pA == pB == null,循环终止,返回null;

2.如果有相交点:

  • 假设链表A的长度为 a+c,链表B的长度为b+c(c为相交部分的长度);
  • pA走过的路径:A--->B,总长度(a+c)+b;
  • pB走过的路径:B--->A,总长度(b+c)+a;

因为(a+c)+b = (b+c)+a,所以pA和pB最终会在相交点相遇;

二、相关算法题目

160.相交链表

经典解法

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if(headA == null || headB == null){return null;}//计算两个链表的长度ListNode currA = headA;ListNode currB = headB;int lengthA = 0;int lengthB = 0;int length = 0;while(currA != null){lengthA++;currA = currA.next; }while(currB != null){lengthB++;currB = currB.next;}//重置指针currA = headA;currB = headB;if(lengthA > lengthB){length = lengthA - lengthB;while(length != 0){currA = currA.next;length--;}}else{length = lengthB - lengthA;while(length != 0){currB = currB.next;length--;}}while(currA != currB){currA = currA.next;currB = currB.next;}return currA;// 返回相交点(或null)}
}

双指针解法

public class Solution {//双指针解法public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if(headA == null || headB == null){return null;}ListNode pA = headA;ListNode pB = headB;while(pA != pB){pA = (pA == null) ? headB : pA.next;pB = (pB == null) ? headA : pB.next;}return pA;}
}

三、总结

1.经典解法里,求完链表A和B的长度以后,记得将currA和currB指针重置,重新指向头节点,否则后面会报错;

2.双指针解法的原理;

关键字:江门seo_建筑公司企业如何成功_百度直播_搜索风云榜

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: