力扣160 / 剑指offer52
https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
这题有坑，题目描述的不清楚。这题意思是节点地址相同（而不只是值）。
思路：让A末尾接上B组成（AB），B的末尾接上A（组成BA），这样两个链表长度就相同了，遍历他们得到相同的节点就是交点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| public class one_six_zero_相交链表 {
@Test
public void test(){
ListNode commons = new ListNode(8);
commons.next= new ListNode(4);
commons.next.next = new ListNode(5);
ListNode headA = new ListNode(4);
headA.next = new ListNode(1);
headA.next.next = commons;
ListNode headB = new ListNode(5);
headB.next = new ListNode(0);
headB.next.next = new ListNode(1);
headB.next.next.next = commons;
ListNode res = getIntersectionNode(headA, headB);
System.out.println(res.val);
}
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null) {
return null;
}
ListNode n1 = headA;
ListNode n2 = headB;
while(n1 != n2){
n1 = n1 == null ? headB : n1.next;
n2 = n2 == null ? headA : n2.next;
}
return n1;
}
}
|
需要注意的是n1 == null而不是n1.next == null，也就是说两个节点都有一次null的机会，否则如果两个链表没有交点，就直接死循环了
评论区看到文艺版解释：
两个结点不断的去对方的轨迹中寻找对方的身影，只要二人有交集，就终会相遇❤
我哭了，程序都比我懂浪漫🙁
其他链表类型的题目点击这里
