那幾題要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;
}
};
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
