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:
null.class Solution {
public:
//计算链表长度
int calcListLength(ListNode *head){
int count = 0;
while (head) {
count++;
head = head->next;
}
return count;
}
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int lengthA = calcListLength(headA);
int lengthB = calcListLength(headB);
ListNode *pA = headA, *pB = headB;
//计算链表长度的差值，较长的先走N步
int n = lengthA - lengthB;
for(int i=0; i<abs(n); i++){
if(n>0){
pA = pA->next;
}else{
pB = pB ->next;
}
}
//同时开始遍历，如相等则为交叉点
while (pB && pA) {
if (pB == pA) {
return pB;
}
pB = pB->next;
pA = pA ->next;
}
return NULL;
}
};
LeetCode 160 ：Intersection of Two Linked Lists
原文：http://blog.csdn.net/sunao2002002/article/details/45727149