一、题目描述
题目：给你两个单链表的头节点 `headA` 和 `headB` ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 `null` 。题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构。
二、题目分析
这种方法的关键是利用两个指针遍历两个链表，当一个指针到达链表末尾时，让它从另一个链表的头部开始遍历，这样在两个链表有交点的情况下，两个指针会在交点相遇。
————————当我走过你来时的路，你也走过我来时的路，那我们就相遇到了一起。————
三、题目代码
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) {* val = x;* next = null;* }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if (headA==null || headB==null){// 如果两个链表中的任意一个为空，返回 nullreturn null;}ListNode currA=headA;//初始化两个指针ListNode currB=headB;while (currA!=currB){// 当两个指针不相等时循环// 如果 currA 到达链表 A 末尾，则让它从链表 B 开始// 如果 currB 到达链表 B 末尾，则让它从链表 A 开始currA=(currA==null)?headB:currA.next;currB=(currB==null)?headA:currB.next;}return currA;}
}
//时间复杂度：O(N + M)，其中 N 和 M 分别是两个链表的长度。两个指针遍历每个链表一次，所以总的时间复杂度是两个链表的长度之和。
//这种方法的关键是利用两个指针遍历两个链表，当一个指针到达链表末尾时，让它从另一个链表的头部开始遍历，这样在两个链表有交点的情况下，两个指针会在交点相遇。