链表/链表相交：返回相交的第一个节点

题目介绍

给你两个单链表的头节点 headA​ 和 headB​ ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null​ 。

图示两个链表在节点 c1​ 开始相交：

​

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

题解

Java

//单链表的定义
public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
   }
}
public class Solution{
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 指针A和指针B走过一样的距离，如果有交点，则是交点；否则就是null指针
        // 对于某个指针，走完当前链表之后，再走另一个链表，从而保证与另一个指针走一样的距离
        if (headA == null || headB == null) return null;
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;//指针A走到末尾之后，再从链表B的头部开始走
            pB = pB == null ? headA : pB.next;//指针B走到末尾之后，再从链表A的头部开始走
        }
        return pA;
    }
}