题目
给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null 。
图示两个链表在节点 c1 开始相交:
思路
假a在链表A上移动,b在链表B上移动,a移动完在B上开始,b移动完再A上开始。最终a移动的距离a + c + x,b移动的距离 b + c + y。可以看到a + c + x = b + c + y,即a + x = b + y ,a移动b距离,b移动a距离a,b指针就会相交,直接返回a,b相交时候a/b指针所指节点的位置。即使a,b没有相交的地方,返回的也是null。
实现
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//怎么保证a链表上的指针下次指到b链表? 一轮就行了 不用考虑
ListNode a = headA;
ListNode b = headB;
while(a != b){
a = a == null ? headB : a.next;
b = b == null ? headA : b.next;
}
return a;
}
}