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.
问题：判断两个列表是否有相交的元素，若有，找出相交节点。
这题也是一道基础题，看了自己的列表知识还需要巩固下才好。
分别求出两个列表的长度 len1, len2 ，以及他们的长度差异 diff
跳过长度差异部分，对于剩余的相同长度部分，依次检查两个链表的对应节点，若又存在相交节点，则必有两个对应节点相等。
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int len1 = ;
ListNode* p1 = headA;
while(p1 != NULL){
p1 = p1->next;
len1++;
}
int len2 = ;
ListNode* p2 = headB;
while(p2 != NULL){
p2 = p2->next;
len2++;
}
p1 = headA;
p2 = headB;
if (len1 > len2){
int diff = len1 - len2;
while(diff > ){
p1 = p1->next;
diff--;
}
}
if (len2 > len1){
int diff = len2 - len1;
while(diff > ){
p2 = p2->next;
diff--;
}
}
while(p1 != NULL ){
if ( p1 == p2){
return p1;
}
p1 = p1->next;
p2 = p2->next;
}
return NULL;
}
参考资料：
LeetCode: Intersection of Two Linked Lists 解题报告, Yu's garden