编写一个程序,找到两个单链表相交的起始节点。
public class FindIntersect {
/**
* 思路:
* 先求出两链表的长度,然后让更长的那个移动到能和更短的那个一样长的位置
* 然后两个一起移动,直到值相等,说明相交了
* @param headA
* @param headB
* @return 相交的节点
*/
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
int lenA = 0;
ListNode temp = headA;
while (temp != null) {
temp = temp.next;
lenA++;
}
int lenB = 0;
temp = headB;
while (temp != null) {
temp = temp.next;
lenB++;
}
if (lenA > lenB) {
for (int i = 0; i < lenA - lenB; i++)
headA = headA.next;
}
else if (lenA < lenB) {
for (int i = 0; i < lenB - lenA; i++)
headB = headB.next;
}
while (headA != null && headB != null) {
if (headA == headB) {
break;
}
headA = headA.next;
headB = headB.next;
}
if (headA == null || headB == null)
return null;
return headA;
}
}