每日算法----链表相交（Java）

双指针

需要找到相交节点，特殊情况两个链表在相交前的节点个数是相同的，这种情况我们只需用两个指针同时遍历两个链表，当currA==currB时，此时就找到了相交节点。

从这个特殊情况可以看出来，我们需要两个链表在相交前的节点个数是相同的，对于两个相交节点不同的情况，当链表A遍历完后，我们让最后一个节点指向链表B，同样的当链表B遍历完之后，我们让链表B的最后一个节点指向链表A。现在这种情况和特殊情况一样了，两个链表在相交前的节点个数是相同的。

文字可能表达的不直观

看上图实例

4->1->8->4->5->5->0->1->8

5->0->1->8->4->5->4->1->8

相交节点为8，前面节点数目相同，这块需要注意的是如果只是当前的值相同不可以，链表是有两个属性的，val和next同时满足才能证明链表相等

public class A06getIntersectionNode {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode currA = headA;
        ListNode currB = headB;

        while (true){
            // 无论是否有无相交，都会在该循环最后走到A，B两个指针相等
            // 有交点，同时指向相交节点 返回相交节点
            // 无交点，同时指向null节点 返回null
            if (currA ==currB){
                return currA;
            }
            if (currA == null){
                currA = headB;// 走完A链表走B链表
            }else {
                currA = currA.next;
            }

            if (currB == null){
                currB = headA;// 走完B链表走A链表
            }else {
                currB = currB.next;
            }
        }
    }
}


 class ListNode {
        int val;
        ListNode next;
        ListNode() {
        }
        ListNode(int val) {this.val = val;}
        ListNode(int val, ListNode next) {this.val = val;this.next = next;}
    }