LeetCode 相交链表

编写一个程序，找到两个单链表相交的起始节点。

 

例如，下面的两个链表：

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3
在节点 c1 开始相交。

 

注意：

如果两个链表没有交点，返回 null.
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
 

致谢:
特别感谢 @stellari 添加此问题并创建所有测试用例。

解法一：

首先，我们计算出两个链表的长度 countA 和 countB，然后计算出它们的差 difference，将较长的那个链表的头指针往后移动 difference 个节点，这样方便后面的遍历操作。然后遍历两个链表，判断它们的节点是否相等，这里是判断它们的引用是否相等，而不是值。因为它们如果是相交链表的话，那么它们的相交节点是同一个节点。找到之后，直接返回相交节点，否则，返回 null。

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        ListNode la = headA;

        ListNode lb = headB;

        ListNode res = null;

        int countA = 0, countB = 0, difference = 0;

        while (la != null) {
            countA++;
            la = la.next;
        }

        while (lb != null) {
            countB++;
            lb = lb.next;
        }

        difference = Math.abs(countA - countB);

        if (countA >= countB) {
            for (int i = 0; i < difference; i++) {
                headA = headA.next;
            }
        } else {
            for (int i = 0; i < difference; i++) {
                headB = headB.next;
            }
        }

        while (headA != null && headB != null) {

            if (headA == headB) {
                return headA;
            }

            headA = headA.next;
            headB = headB.next;
        }
        return res;
    }