160. Intersection of Two Linked Lists
创新互联成立10余年来，这条路我们正越走越好，积累了技术与客户资源，形成了良好的口碑。为客户提供成都网站建设、成都做网站、网站策划、网页设计、域名注册、网络营销、VI设计、网站改版、漏洞修补等服务。网站是否美观、功能强大、用户体验好、性价比高、打开快等等，这些对于网站建设都非常重要，创新互联通过对建站技术性的掌握、对创意设计的研究为客户提供一站式互联网解决方案，携手广大客户，共同发展进步。
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.
题目大意：
找出两个链表后半部分的交汇点。
思路：
1.求出两个链表的长度。
2.获取链表长度差n。
3.将长的链表先移动到第n个节点。
4.对长链表和短链表进行比较。(同时向后移动)如果在链表尾之前找到相等的节点，返回该节点，如果没找到，返回NULL。
代码如下：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
int listLength(ListNode *head)//用快指针求链表长度
{
ListNode * p = head;
int i = 0 ;
while(p && p->next)
{
i++;
p = p->next->next;
}
if(p == NULL)
return 2 * i;
return 2 * i + 1;
}
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int lenA = listLength(headA);
int lenB = listLength(headB);
int maxLen = lenA > lenB ? lenA :lenB;
int remain ;
ListNode * la,*lb;
la = headA;
lb = headB;
if(maxLen == lenA)
{
remain = lenA - lenB;
while(remain--)
{
la = la->next;
}
}
else
{
remain = lenB - lenA;
while(remain--)
lb = lb->next;
}
while(lb != NULL)
{
if(la != lb)
{
la = la->next;
lb = lb->next;
}
else
{
return la;
}
}
return NULL;
}
};2016-08-13 01:08:14