力扣 剑指 Offer 52. 两个链表的第一个公共节点

题目来源：https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/

大致题意：
给两个链表，它俩从某个节点开始剩下的部分都重合，找出它们第一个公共节点，也就是重合节点。

思路

遍历查找

1. 先遍历一个链表，使用set存下所有节点
2. 再遍历另一个链表，每次都查找当前节点是否在set中，若在则代表为公共节点，第一次碰到的也就是第一个公共节点，直接返回
   时间复杂度O(m+n)，空间复杂度O(m)

差值法

1. 先遍历获取两个链表长度
2. 计算长度差值diff
3. 然后先遍历长的那个链表前diff个节点
4. 同步遍历两个链表，直至找到相同节点

时间复杂度O(m+n)，空间复杂度O(1)。
但是因为该方法不用查找Set，直接遍历链表，因而执行速度会更快。
代码：

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 方法一，遍历查找
        // Set<ListNode> visited = new HashSet<ListNode>();    
        // ListNode temp = headA;
        // while (temp != null) { // A所有节点入集合
        //     visited.add(temp);
        //     temp = temp.next;
        // }
        // temp = headB;
        // while (temp != null) { // 查找B当前节点是否在A中
        //     if (visited.contains(temp)) { // 若有则代表为第一个公共节点
        //         return temp;
        //     }
        //     temp = temp.next;
        // }

        // return null;

        // 方法二，差值法
        ListNode tempA, tempB;
        tempA = headA;
        tempB = headB;
        int lengthA, lengthB;
        lengthA = 0;
        lengthB = 0;
        // 获取链表长度
        while (tempA != null && lengthA++ >= 0)   tempA = tempA.next;
        while (tempB != null && lengthB++ >= 0)   tempB = tempB.next;
        // 获取差值
        int diff = lengthA - lengthB;
        // 谁长谁先走diff步
        if (diff > 0) { // A长
            while(diff-- > 0) {
                headA = headA.next;
            }
        }
        else { // B长
            diff = -diff; // 先变正
            while(diff-- > 0) {
                headB = headB.next;
            }
        }

        while (headA != headB) { // 查找公共节点
            headA = headA.next;
            headB = headB.next;
        }

        return headA;
    }