题目描述
找到两个单链表相交的起始节点。
如下面的两个链表：

在节点 c1 开始相交。

注意：
如果两个链表没有交点，返回 null.
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
复杂度分析

双指针法

核心一点就是得知道，如果不存在环，两个链表相交，那么他们的尾节点一定是相同的。
show code

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null || headB==null){
            return null;
        }
        ListNode aTail=headA;
        ListNode bTail=headB;
        int alength=1;
        int blength=1;
        while(aTail.next!=null){
            aTail = aTail.next;
            alength++;
        }
         while(bTail.next!=null){
            bTail = bTail.next;
            blength++;
        }
        if(!aTail.equals(bTail)){//判断两个链尾是否在是同一个节点，如果相交一定是同一个节点
            return null;
        }
        ListNode shortPonit = headA;
        ListNode longPonit = headB;
        int sub =Math.abs(alength-blength);
        if(alength>blength){
            shortPonit = headB;
            longPonit=headA;
        }
        while(sub>0){//长链表的指针先走sub步，保证未遍历的长度和短链表相等
            longPonit=longPonit.next;
            sub--;
        }
        while(!longPonit.equals(shortPonit)){//移动到第一个相等的节点，即为交点
            longPonit = longPonit.next;
            shortPonit=shortPonit.next;
        }
        return shortPonit;
    }

上面代码比较直观，但是略显啰嗦。
可以换个方式消除长度差：拼接两链表。
如图，两指针分别先后遍历两链表第一个相等的点就是相交点。

show code

  public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null) return null;
        ListNode apointer = headA;
        ListNode bpointer = headB;
        while(apointer != bpointer){
            apointer = (apointer == null ? headB : apointer.next);
            bpointer = (bpointer == null ? headA : bpointer.next);
        }
        return apointer;
    }

时间复杂度 : O(m+n)
空间复杂度 : O(1)

其他解法

问题转化为判断一个链表是否有环问题

这个问题我们可以转换为另一个等价问题：如何判断一个单链表是否有环，若有环，找出环的入口？

如何转化？
先遍历第一个链表到它的尾部，然后将尾部的next指针指向第二个链表(尾部指针的next本来指向的是null)。这样两个链表就合成了一个链表。若该链表有环，则原两个链表一定相交。否则，不相交。

暴力法

对链表A中的每一个结点，遍历整个链表B并检查链表B中是否存在结点相同。

复杂度分析
时间复杂度 : (mn)
空间复杂度 : O(1)

哈希表法

遍历链表 A 并将每个结点的地址/引用存储在哈希表中。然后检查链表B中的每一个结点 是否在哈希表中。若在，则为相交结点。

复杂度分析
时间复杂度 : O(m+n)
空间复杂度 : O(m)或 O(n)