1. //编写一个程序，找到两个单链表相交的起始节点。 
  2. //
  3. // 如下面的两个链表： 
  4. //
  5. // 
  6. //
  7. // 在节点 c1 开始相交。 
  8. //
  9. // 
  10. //
  11. // 示例 1： 
  12. //
  13. // 
  14. //
  15. // 输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, s
  16. //kipB = 3
  17. //输出：Reference of the node with value = 8
  18. //输入解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1
  19. //,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
  20. // 
  21. //
  22. // 
  23. //
  24. // 示例 2： 
  25. //
  26. // 
  27. //
  28. // 输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB =
  29. // 1
  30. //输出：Reference of the node with value = 2
  31. //输入解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4
  32. //]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
  33. // 
  34. //
  35. // 
  36. //
  37. // 示例 3： 
  38. //
  39. // 
  40. //
  41. // 输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
  42. //输出：null
  43. //输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而
  44. // skipA 和 skipB 可以是任意值。
  45. //解释：这两个链表不相交，因此返回 null。
  46. // 
  47. //
  48. // 
  49. //
  50. // 注意： 
  51. //
  52. // 
  53. // 如果两个链表没有交点，返回 null. 
  54. // 在返回结果后，两个链表仍须保持原有的结构。 
  55. // 可假定整个链表结构中没有循环。 
  56. // 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。 
  57. // 
  58. // Related Topics 链表 
  59. // 👍 857 👎 0

链表的相交问题。

暴力法

两个链表依次循环比较，找到那个相交的链表。
时间复杂度： 两个链表要循环比较，时间复杂度O(M*N)
代码比较丑陋。

哈希表

将链表A的节点放入哈希表中，循环链表B寻找相等的节点。
时间复杂度：O(M+N)
空间复杂度：O(M). 需要将链表A放入哈希表中。


public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> set = new HashSet<>();
        ListNode point = headA;
        while (point != null){
            set.add(point);
            point = point.next;
        }

        point = headB;
        while (point != null){
            if (set.contains(point)){
                return point;
            }
            point = point.next;
        }
        return null;
    }
}

指针遍历

忘记了从哪看到的，链表有环的情况，只要一个快指针一个慢指针，他们重合的时候就是这个链表成环的时候。
这题双指针的问题在于，并不能确定两个链表长度相同，也即重合前的长度不一定相同。如果两个指针同时比较并后移的话，可能出现的情况是，一个已经进入重合部分，一个还没进入。这就错过了重合部分的判断。
解决方法是如果一个链表已经遍历结束，就将该指针指向另一个链表。
这样做的目的是保证两个链表长度相同。遍历A，总遍历长度就是 M+N， 遍历B，总遍历长度是N+M。
image.png
假设两个链表是这样，红色部分表示重合。
那么两个链表拼接之后就是这样
image.png
可以看到，两个链表即使前面长度不同，但是遍历到之后，依然有着共同的重合部分。
因此链表AB遍历到最后的时候会在相同的位置进入重合部分。
时间复杂度 ： O(M+N)
没有使用额外空间。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode point1 = headA;
        ListNode point2 = headB;

        while (point1 != point2){
            point1 = point1 == null ? headB : point1.next;
            point2 = point2 == null ? headA : point2.next;
        }
        return point1;
    }
}