题目

• 两个链表重叠查找：给定两个链表，有可能链表从某一个节点开始就完全重叠，需要返回重叠部分的第一个节点值，如果没有重叠部分就返回null
• 要求时间复杂度O(n),空间复杂度O(1)

解析

• 如果不给定限制条件，这道题的做法有三种：
• 第一种：我以第一个链表或者第二个链表作为匹配值，然后遍历另一个链表是否和当前值相等，就可以找到对应的值或者返回null,时间复杂度O(mn)空间复杂度O(1)
• 第二种：将链表A或者B存储到哈希表中，然后利用哈希特性查找另一个链表是否含有其中的值，第一个含有的即为开始值，整个查找都没有结果返回null,空间复杂度O(n)或者O(m)时间复杂度O(m+n)
• 第三种：按照数学特性，我假设一个节点first从A开始走，一个节点second从B开始走，当first走到A最后时此时从B的开始走，反之second从A开始走，如果他们有重叠部分，那么一定会在第一个值重叠的地方返回，如果整个遍历完成都没有重叠的值那么久返回null。如下图中所示：从A走过到C的距离就是x+z+y,同理从B走过的就是y+z+x这两个是相等的，所以可解。且满足题目要求O(m+n)空间复杂度O(1)

源代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode first = headA, second = headB;
        boolean markedA = false, markedB = false;
        while (first != null && second != null) {
            if (first == second) return first;//找到对应的节点
            if (first.next == null && !markedA) {
                first = headB;
                markedA = true;
            } else first = first.next;
            if (second.next == null && !markedB) {
                second = headA;
                markedB = true;
            } else second = second.next;
        }
        return null;
    }
}