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
}
