Q:
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.
A:
可以处理no intersection case。
没变要处理距离diff，没必要考虑value，没必要map/look up。
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
ListNode p1 = headA;
ListNode p2 = headB;
while (p1 != null && p2 != null & p1 != p2){
p1 = p1.next;
p2 = p2.next;
if (p1 == p2) return p1; //即便no intersection，p1和p2也都已经指向null了
if (p1 == null) p1 = headB;
if (p2 == null) p2 = headA;
}
return p1;
}
}
最关键的思想：如果iteration了一整个ListNodes都reach到null了，那么使其指向另外一个List的head。如果没有intersection，（那么另外一个pointer reach到null的时候，也同样指向另外一个List的head，）最终，两个pointer都会遍历自己的ListNodes和对方List的ListNodes，所以会 同时 reach到对方最后的一个节点（null）。这个时候p1=p2, p1=null, p2=null。
还有种写法（Java 问号表达式，三目运算）：
p1 = ( p1 == null ? headB : p1.next ); p2 = ( p2 == null ? headA : p2.next );
a = b ? c : d 如果b的条件成立，赋值a = c, 否则 a = d。
