大家的题解都是双指针双百解法。
我来说一个这题的实际应用:
求两个类最低一层的公共父类,就是两个树节点最低一层的公共祖先节点。
这里的树节点内容不是left和right,而是指向父节点的指针。
两个类都用.getSuperclass()方法生成直到Object的两个链表,
再调用这个题的方法就求出了第一个公共祖先。
public class Solution {
public ListNode FindFirstCommonNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null) return null;
ListNode a = headA, b = headB;
int len1 = 0, len2 = 0, sum = 0;
while(a != null && ++len1 > 0) a = a.next;
while(b != null && ++len2 > 0) b = b.next;
a = headA;
b = headB;
while (a != b){
if(a.next == null) a = headB;
else a = a.next;
if(b.next == null) b = headA;
else b = b.next;
if(sum++ > len1 + len2) return null;
}
return a;
}
}
京公网安备 11010502036488号