那几题要15刀才能测试的就先放着了。先吧可以在线测试的刷了。
这题是找到零个链表的相交的那个节点。如果没有相交，那就返回NULL。
思路一：
如果有相交，那么他们相交点之后的节点肯定都是共有的，然后两个链表有长有短的话，就先把长的读到和短的一样长，然后两个人在同时走，走到第一个相同的点就是答案了。如果相同的点是NULL了，那就是没有相交点。
/*
*
* 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
*l1 = headA, *l2 =
headB;
if
(!headA || !headB)
return
NULL;
int
cnt1 =
0
, cnt2 =
0
;
while
(l1)
{
cnt1
++; l1 = l1 ->
next;
}
while
(l2)
{
cnt2
++; l2 = l2 ->
next;
}
if
(cnt1 >
cnt2)
{
l1
= headA; l2 =
headB;
int
tmpcnt1 = cnt1 -
cnt2;
while
(tmpcnt1-- >
0
)
l1
= l1 ->
next;
}
else
{
l2
= headB; l1 =
headA;
int
tmpcnt2 = cnt2 -
cnt1;
while
(tmpcnt2-- >
0
)
l2
= l2 ->
next;
}
while
(l1 && l2 && l1 !=
l2)
{
l1
= l1 ->
next;
l2
= l2 ->
next;
}
if
(l1 ==
l2)
return
l1;
return
NULL;
}
};
思路二：
因为两个链表长度可能不一样长，所以不能从第一次走一样的距离判断相交点，但是。可以这样，两个链表同时走，走到末尾后，分别将指针跳到另一个链表的开头，这样，他们第一次相同的点就是答案了。
/*
*
* 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
*l1 = headA, *l2 =
headB;
if
(!headA || !headB)
return
NULL;
while
(l1 &&
l2)
{
l1
= l1 ->
next;
l2
= l2 ->
next;
}
if
(!
l1)
{
l1
=
headB;
while
(l1 &&
l2)
{
l1
= l1 ->
next;
l2
= l2 ->
next;
}
l2
=
headA;
while
(l1 && l2 && l1 !=
l2)
{
l1
= l1 ->
next;
l2
= l2 ->
next;
}
}
else
{
l2
=
headA;
while
(l1 &&
l2)
{
l1
= l1 ->
next;
l2
= l2 ->
next;
}
l1
=
headB;
while
(l1 && l2 && l1 !=
l2)
{
l1
= l1 ->
next;
l2
= l2 ->
next;
}
}
if
(l1 !=
l2)
return
NULL;
return
l1;
}
};
