##问题描述
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.
即要寻找相交节点,并且要求时间复杂度为n,空间复杂度为1
##问题分析
该问题解决方法非常巧妙
利用list中的val值,计算listB中的所有节点val的和countB
然后计算listA中val++和的值,最后再次计算listB中val的值得和newCountB
比较一下countB和newCountB,如果两者相同,说明listB没有受到listA的影响,则listA和listB无交点
否则则说明有交点,并且交点位置为lengthB - newCountB-countB
Tip:这个方法太牛逼了(不是我想到的)
##C++代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *tmp = headB;
int countB = 0,lengthB = 0;
while(tmp != NULL){
countB += tmp->val;
tmp = tmp->next;
lengthB++;
}
tmp = headA;
while(tmp != NULL){
tmp->val++;
tmp = tmp->next;
}
tmp = headB;
int newCountB = 0;
while(tmp != NULL){
newCountB += tmp->val;
tmp = tmp->next;
}
//默认不允许修改list的结构,所以要将其还原
tmp = headA;
while (tmp!=NULL)
{
tmp->val--;
tmp = tmp->next;
}
if(newCountB == countB) return NULL;
//应该写成if else结构的,但是实际这两种写法的效果是一样的
tmp = headB;
for(int i = 0;i < lengthB-(newCountB-countB);i++){
tmp = tmp->next;
}
return tmp;
}
};