编写一个程序可以找出两个单向链表的的第一个相交的节点。

例如，下图的两个链表：

在 c1 节点开始相交。

例一：

输入： intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出： 值为 8 的节点。
输入解释： 相交节点的值是 8（如果两个链表相交这个值一定不为 0）。从 A 的头部开始，A 可以表示为 [4,1,8,4,5]。从 B 的头部开始，B 可以表示为 [5,0,1,8,4,5]。A 在相交节点前有 2 个节点，B 在相交节点前有 3 个节点。

例二：

输入： intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出： 值为 2 的节点。
输入解释： 相交节点的值是 2（如果两个链表相交这个值一定不为 0）。从 A 的头部开始，A 可以表示为 [0,9,1,2,4]。从 B 的头部开始，B 可以表示为 [3,2,4]。A 在相交节点前有 3 个节点，B 在相交节点前有 1 个节点。

例三：

输入： intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出： null
输入解释： 从 A 的头部开始，A 可以表示为 [2,6,4]。从 B 的头部开始，B 可以表示为 [1,5]。因为两个链表没有相交，intersectVal 一定是 0，同时 skipA 和 skipB 可以为任意值。
解释： 两个链表没有相交，所以返回 null。

提示：
1. 如果两个链表没有相交，返回 null。
2. 在函数返回结果后，两个链表必须保持原有结构。
3. 你可以认定在链表中不存在循环链表。
4. 你的代码的时间复杂度应当为 O(n)，空间复杂度为 O(1)。

这个题和环形链表有点异曲同工，也是在走过的距离上做文章。使用双指针，第一个指针在第一个链表上走完之后走第二个链表，第二个指针在第二个链表上走完之后走第一个链表，这样，如果有相交节点两个指针一定会在某个时刻指向同一个节点，而没有相交时两个指针则会同时指向 null，也正好是我们需要的结果。

/*
 * 160. Intersection of Two Linked Lists
 * https://leetcode.com/problems/intersection-of-two-linked-lists/
 * https://www.whosneo.com/160-intersection-of-two-linked-lists/
 */
public class GetIntersectionNode {
    public static void main(String[] args) {
        ListNode head1 = new ListNode(4);
        head1.next = new ListNode(1);
        head1.next.next = new ListNode(8);
        head1.next.next.next = new ListNode(4);
        head1.next.next.next.next = new ListNode(5);
        ListNode head2 = new ListNode(5);
        head2.next = new ListNode(0);
        head2.next.next = new ListNode(1);
        head2.next.next.next = head1.next.next;

        GetIntersectionNode solution = new GetIntersectionNode();

        ListNode node = solution.getIntersectionNode(head1, head2);
        if (node != null)
            System.out.println(node.val);
    }

    private ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode nodeA = headA, nodeB = headB;

        while (nodeA != nodeB) {
            nodeA = nodeA == null ? headB : nodeA.next;
            nodeB = nodeB == null ? headA : nodeB.next;
        }

        return nodeA;
    }
}