目录
一、相交链表思路
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.双指针解法的原理;