160 Intersection of Two Linked L

Write a program to find the node at which the intersection of two singly linked lists begins.

Example：

举例略，就是两个链表，最后会合在一起（也可能不合在一起），求出最先合在一起的点

1. 暴力

实际耗时：640ms

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode l1 = headA;
    while (l1 != null) {
        ListNode l2 = headB;
        while (l2 != null) {
            if (l1 == l2) {
                return l1;
            } else {
                l2 = l2.next;
            }
        }
        l1 = l1.next;
    }
    return l1;
}

  思路很简单，对于A的每个节点，遍历B的每个节点，去寻找有没有一样的。

时间复杂度O(nm) n和m分别是两个链表的长度。

空间复杂度O(1)

2. 利用HashSet

实际耗时：7ms

public ListNode getIntersectionNode3(ListNode headA, ListNode headB) {
    Set<ListNode> set = new HashSet<>();
    ListNode l1 = headA, l2 = headB;
    while (l1 != null) {
        set.add(l1);
        l1 = l1.next;
    }
    while (l2 != null) {
        if (set.contains(l2)) {
            return l2;
        }
        l2 = l2.next;
    }
    return null;
}

  思路就是在方法一的基础上，加了一个hashset来加速查找的效率

时间复杂度O(m+n) m为l1的长度 n为l2的长度

空间复杂度O(m) m为l1的长度

3. 最巧妙的方法

实际耗时：1ms

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode l1 = headA, l2 = headB;
    while (l1 != l2) {
        l1 = (l1 == null) ? headB : l1.next;
        l2 = (l2 == null) ? headA : l2.next;
    }
    return l1;
}

  思路其实说破了很简单，假设headA到交点是需要a步，而headB到交点需要b步，之后大家都需要c步走到最后。这里假设a<b，那l1会先走到最后，然后然l1再去从headB的路，然后l2之后再去走headA的路就行了，这样当它们一样的时候就是走到交点了，相当于a + c + b = b + c + a。自己画个图会更简单。

时间复杂度O(n+m)

空间复杂度O(1)