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.
?
本題的思路還是比較多的，我剛開始想了幾個最后做出來后參考解決方法耶有幾個我總結如下：
方法一：將headA先遍歷到最后然后將結尾鏈接到headA頭部，構造成了一個有環的鏈表然后然后利用一個指針一個慢指針去跑，具體怎么找可以參考我前面寫過的那個”Linked List Cycle II“=======》最后結果是正確的但是結果說不讓修改鏈表結構。
?
方法二：先求出headA和headB的長度然后算出headA和headB的長度差，長度差就是A或者B多出來的長度，減去長度差然后同時往后遍歷即可找到相交的點，小提示：在求headA和headB長度的時候比較一下最后的那個節點，如果不相等則肯定沒有交點。=======》算法通過 時間復雜度O（m+n）
方法三：暴力比較，時間復雜度O（mn）。
方法四：分別遍歷A和B，放入hash中進行比較，如果有出現相同hash則為相交點。
方法五：用兩個指針A，B去遍歷headA和headB，A從headA遍歷到最后時，轉到headB頭開始遍歷。反之，B從headB轉到A，每次比較一次節點，如果相同則為相交點。時間復雜度O（n+m）
?
我感覺方法五是很牛逼的。。。。。我只是實現了方法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
}
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
