解答
在节点 c1 开始相交。
注意:
1.如果两个链表没有交点,返回 null.
2.在返回结果后,两个链表仍须保持原有的结构。
3.可假定整个链表结构中没有循环。
4.程序尽量满足 O(n) 时间复杂度,且仅用 O(1) 内存。
/**
* 返回相交单向链表的交点
*/
public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
//记录链表的长度
int lenA = 1;
ListNode tempA = headA;
while (tempA.next != null) {
lenA++;
tempA = tempA.next;
}
int lenB = 1;
ListNode tempB = headB;
while (tempB.next != null) {
lenB++;
tempB = tempB.next;
}
//判断链表是否相交,不想交直接返回null
if (!tempA.equals(tempB)) {
return null;
}
//截取后半段,相同长度的链表
int reduseCount = lenA - lenB;
tempA = headA;
tempB = headB;
if (reduseCount > 0) {
for (int i = 0; i < reduseCount; i++) {
tempA = tempA.next;
}
} else {
reduseCount = Math.abs(reduseCount);
for (int i = 0; i < reduseCount; i++) {
tempB = tempB.next;
}
}
//循环遍历找到交点
while (tempB != null && tempA != null) {
if (tempB.equals(tempA)) {
return tempB;
}
tempA = tempA.next;
tempB = tempB.next;
}
return null;
}
帖子还没人回复快来抢沙发