hot100 160.相交链表

思路：

1.算法流程：

（1）初始化两个指针：p = headA,q = headB。

（2）不断循环，直到p = q。

（3）每次循环，p和q各走一步。具体来说：如果p不是空节点，那么更新p为p.next，否则更新p为headB；如果q不是空节点，那么更新q为q.next，否则更新q为headA。

（4）循环结束时，如果两条链表相交，那么此时p和q都在相交的起始节点处，返回p；如果两条链表不相交，那么p和q都在空节点，所以也可以返回p，即空节点。

2.复杂度分析：

（1）时间复杂度：O(m + n)，其中m是第一条链表的长度，n是第二条链表的长度。除了交点，每个节点都会被指针p访问至多一次，每个节点都会被指针q访问至多一次。

（2）空间复杂度：O(1)。

附代码：

public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode p = headA; ListNode q = headB; while(p != q){ p = p != null ? p.next : headB; q = q != null ? q.next : headA; } return p; } }