江门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.双指针解法的原理；