leetcode 链表相交

面试题 02.07. 链表相交 - 力扣（LeetCode） (leetcode-cn.com)

在看别人的题解之前我有过两个思路。

1.最容易想到的就是对链表A中的每个元素都在B中查找，如果找到了就是相交点，显然这种方法的时间复杂度比较高，leetcode执行用时是709ms。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA==null||headB==null)
            return null;
        ListNode Anode = headA;
        ListNode Bnode = null;
        while (Anode!=null){
            Bnode = headB;
            while (Bnode!=null){
                if(Anode==Bnode)
                    return Anode;
                Bnode = Bnode.next;
            }
            Anode = Anode.next;
        }

        return null;
    }
}

2.第一种的时间太长了，我就想改进一下，想到了用Set记录遍历过的结点，如果某一次add(node)之后Set.size()没有变，就说明这个node就是相交点。leetcode执行时间13ms.

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA==null||headB==null)
            return null;
        ListNode Anode = headA;
        ListNode Bnode = headB;

        Set<ListNode> set = new HashSet<>();
        int size = 0;

        while (Anode!=null&&Bnode!=null){
            size = set.size();
            set.add(Anode);
            if (size == set.size())
                return Anode;
            size = set.size();
            set.add(Bnode);
            if(size == set.size())
                return Bnode;

            Anode = Anode.next;
            Bnode = Bnode.next;
        }

        if (Anode==null&&Bnode!=null){
            while (Bnode !=null){
                size = set.size();
                set.add(Bnode);
                if(size == set.size())
                    return Bnode;
                Bnode = Bnode.next;
            }
        }
        if (Bnode==null&&Anode!=null){
            while (Anode !=null){
                size = set.size();
                set.add(Anode);
                if(size == set.size())
                    return Anode;
                Anode = Anode.next;
            }
        }

        return null;
    }
}

3.看了别人的题解，有一种更好的方法：假设链表A和B的长度分别是n,m(n>m)，就让链表A先走(n-m)步，此时A和B就是一种“并驾齐驱”的状态，之后A，B一起向后遍历，遇到的第一个相同的结点就是相交点。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = 0;
        int lenB = 0;
        ListNode Anode = headA;
        ListNode Bnode = headB;
        while (Anode != null) {
            lenA++;
            Anode = Anode.next;
        }
        while (Bnode != null) {
            lenB++;
            Bnode = Bnode.next;
        }
        int diff;
        if (lenA < lenB) {
            diff = lenB - lenA;
            ListNode temp = headA;
            headA = headB;
            headB = temp;
        } else {
            diff = lenA - lenB;
        }
        while (diff-- != 0) {
            headA = headA.next;
        }
        while (headA != null && headB != null) {
            if (headA == headB)
                return headA;
            headA = headA.next;
            headB = headB.next;
        }
        return null;
    }
}