相交链表

理解题目：

给定两个单链表，判断它们是否相交，如果相交，返回相交的起始节点，否则返回 null。

代码实现：

public class IntersectionOfTwoLinkedLists {
    // 相交链表
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }

        ListNode pA = headA;
        ListNode pB = headB;

        // 如果两个指针没有相遇，就分别移动到另一个链表的头部
        while (pA != pB) {
            pA = (pA == null) ? headB : pA.next;
            pB = (pB == null) ? headA : pB.next;
        }

        return pA;
    }
}

步骤解释：

初始化两个指针 pA 和 pB 分别指向两个链表的头部。
在每一次迭代中，判断两个指针是否相等，如果相等说明相交，直接返回其中一个指针即可。
如果两个指针没有相遇，则分别移动到另一个链表的头部继续遍历。
当两个指针相遇时，返回其中一个指针即为相交的起始节点，如果没有相交，则最终两个指针都会指向 null。

时间复杂度： 由于两个指针分别遍历了两个链表，时间复杂度为 O(m + n)，其中 m 和 n 分别是两个链表的长度。

空间复杂度： 只使用了常数级别的额外空间，空间复杂度为 O(1)。