Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
begin to intersect at node c1.
Notes:
- If the two linked lists have no intersection at all, return
null
. - The linked lists must retain their original structure after the function returns.
- You may assume there are no cycles anywhere in the entire linked structure.
- Your code should preferably run in O(n) time and use only O(1) memory.
Solution 1: 先把2 list移动到等长位置,再同时移动,直到找到交点
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null){
return null;
}
int l1 = findLength(headA), l2 = findLength(headB);
if(l1 < l2){
ListNode temp = headA;
headA = headB;
headB = temp;
}
for(int i = 0; i < Math.abs(l1 - l2); i++){
headA = headA.next;
}
if(headA == headB){
return headA;
}
while(headA != null){
if(headA.next == headB.next){
return headA.next;
}
headA = headA.next;
headB = headB.next;
}
return null;
}
private int findLength(ListNode head){
int length = 0;
while(head != null){
length++;
head = head.next;
}
return length;
}
Solution 2:
1) 找到第一个Linked List的最后一个node, 将其和第二个Linked List的head相连
2) 若两个Linked List相交,则一定会形成一个环(若无环则证明不相交,返回null)
3) 再以第一个Linked List的head为起点寻找环的起点即可
4) 为保持两个Linked List结构,最后要将第一个Linked List的最后一个节点指向null