题目:
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
.思路分析:
因为两个List的长度不一样,所以先分别算出两个List的长度,然后设置一个指针指向较长的List的(长-短)的位置,这样子较长List从该位置开始到最后的长度和较短List相同,然后遍历两个List如果有相同的Node则返回。
代码示例:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution
{
private:
int length(ListNode *head)
{
int count = 0;
ListNode *p = head;
while (p)
{
count++;
p = p->next;
}
return count;
}
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
{
if (headA == NULL || headB == NULL)
{
return NULL;
}
int lengthA = length(headA);
int lengthB = length(headB);
int offLength = lengthA - lengthB;
if (offLength < 0)
{
offLength *= -1;
}
ListNode *pa = headA;
ListNode *pb = headB;
for (int i = 0; i < offLength; i++)
{
if (lengthA > lengthB)
{
pa = pa->next;
}
else
{
pb = pb->next;
}
}
while (pa != pb)
{
pa = pa->next;
pb = pb->next;
}
return pa;
}
};