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.
?
本題的思路還是比較多的，我剛開始想了幾個(gè)最后做出來后參考解決方法耶有幾個(gè)我總結(jié)如下：
方法一：將headA先遍歷到最后然后將結(jié)尾鏈接到headA頭部，構(gòu)造成了一個(gè)有環(huán)的鏈表然后然后利用一個(gè)指針一個(gè)慢指針去跑，具體怎么找可以參考我前面寫過的那個(gè)”Linked List Cycle II“=======》最后結(jié)果是正確的但是結(jié)果說不讓修改鏈表結(jié)構(gòu)。
?
方法二：先求出headA和headB的長(zhǎng)度然后算出headA和headB的長(zhǎng)度差，長(zhǎng)度差就是A或者B多出來的長(zhǎng)度，減去長(zhǎng)度差然后同時(shí)往后遍歷即可找到相交的點(diǎn)，小提示：在求headA和headB長(zhǎng)度的時(shí)候比較一下最后的那個(gè)節(jié)點(diǎn)，如果不相等則肯定沒有交點(diǎn)。=======》算法通過 時(shí)間復(fù)雜度O（m+n）
方法三：暴力比較，時(shí)間復(fù)雜度O（mn）。
方法四：分別遍歷A和B，放入hash中進(jìn)行比較，如果有出現(xiàn)相同hash則為相交點(diǎn)。
方法五：用兩個(gè)指針A，B去遍歷headA和headB，A從headA遍歷到最后時(shí)，轉(zhuǎn)到headB頭開始遍歷。反之，B從headB轉(zhuǎn)到A，每次比較一次節(jié)點(diǎn)，如果相同則為相交點(diǎn)。時(shí)間復(fù)雜度O（n+m）
?
我感覺方法五是很牛逼的。。。。。我只是實(shí)現(xiàn)了方法2.
具體代碼如下：
1
/**
2
* Definition for singly-linked list.
3
* public class ListNode {
4
* int val;
5
* ListNode next;
6
* ListNode(int x) {
7
* val = x;
8
* next = null;
9
* }
10
* }
11
*/
12
public
class
Solution {
13
public
ListNode getIntersectionNode(ListNode headA, ListNode headB) {
14
if
(headA==
null
||headB==
null
)
return
null
;
15
ListNode list1=
headA;
16
ListNode list2=
headB;
17
int
len1=1,len2=1
,length;
18
while
(list1.next!=
null
){
19
list1=
list1.next;
20
len1++
;
21
}
22
while
(list2.next!=
null
){
23
list2=
list2.next;
24
len2++
;
25
}
26
if
(list1.val!=list2.val)
return
null
;
27
if
(len1-len2>0
){
28
length=len1-
len2;
29
for
(
int
i=0;i<length;i++
){
30
headA=
headA.next;
31
}
32
}
33
else
{
34
length=len2-
len1;
35
for
(
int
i=0;i<length;i++
){
36
headB=
headB.next;
37
}
38
}
39
while
(headA!=
null
){
40
if
(headA.val==headB.val)
return
headA;
41
headA=
headA.next;
42
headB=
headB.next;
43
}
44
return
null
;
45
}
46
47
48
}
?
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
