leetcode160相交链表

看到这道题首先想到的是两个链表相交的部分只可能出现在两个链表的尾部，接着就自然想到了使用两个指针来逐个对比ListNode的值，就有了接下来的方法：

简单的想法

由于两个链表长度不一定一致，而且我们在遍历一次链表之前没有办法知道两个链表各自的长度，这就导致了我们并能确定从第几个节点开始进行比较，但是可以明确的是，相交的位置肯定不会是长链表的前k个节点，这里k = ListA.size() - ListB.size()，假设A的长度要长于B，而且两个链表一定会有相交的部分。如果我们知道了这个k值，就可以从长链表的第k个元素，短链表的头部开始进行逐个的比较。当有相等的元素时，便设置这个交点，如果发现了不相等的节点，便将交点设置为null，直到遍历到列表结尾。这种想法可以用以下代码来描述

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode result = null;
        ListNode pa = headA,pb = headB;
        int diff = 0;
        // 计算长度之差
        while(pa!=null){ 
            diff++;
            pa = pa.next;
        }
        while(pb!=null){   
            diff--;
            pb = pb.next;
        }
        pa = headA;
        pb = headB;
        // 移动长链表指针到指定位置
        if(diff >= 0){
            while(diff-- > 0) {
                pa = pa.next;
            }
        }else{
            while(diff++ < 0){
                pb = pb.next;
            }
        }
        // 从当前位置开始比较
        while(pa != null && pb != null){
            if(pa!=pb){
                result = null;
            }else if(pa == pb && result == null){
                result = pa;
            }
            pa = pa.next;
            pb = pb.next;
        }
        return result;
    }
}

值得注意的是，题目中所说的相交链表并不是指给出两条链表如
这样子分开的两条链表，而是形如
这样子的结构，所以在题目描述case1中（如下图）得到的交点位置并不是1，而是8.

避免上述问题的具体方法是在比较时不去比较两个指针指向节点的value，而是直接比较两个指针指向的是否时同一个节点。

上述的方法是可以解决问题的，但是代码是不够优雅，而且可以看出代码冗长的原因是事先对两个链表的长度差的处理。

优雅的方式

既然两个链表的长度差带来了大量的代码，那么有没有办法解决这个问题呢？正如开头就已经说过的，如果两个链表有相交，那么二者相交的部分只可能存在于两个链表的尾巴上。而且解决这个问题的关键在于解决两个链表的长度差。
既然交点存在于尾部，那么不妨把两个链表进行拼接，如图

如图，我们可以将两条链表在逻辑上区分开，并将链表A拼接到链表B上，将链表B拼接到链表A上，这样，新得到的两条链表长度是完全一样的（黑色圈住的就是两条链表的长度差）。而且，相交的部分仍然出现在结尾，同时可以想象，如果两个指针从头开始遍历，如果有交点，那么当两个指针第一次指向同一个节点时，就是我们想要的结果，而如果两个链表根本没有共同部分时，两个指针第一次相等的位置就是NULL。另外，当两条链表长度相等时，我们最远只会遍历到第一次出现的Null，如
1-3-5-null 和 2-4-6-null 还有1-3-5-null和2-4-5-null，也是容易想象的。

逻辑上，我们并不需要真正的将两条链表真正相接，只需要在遍历完一条链表时将指针移动到另一条链表的头部。于是，可以写出如下代码：

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pa = headA,pb = headB;
        while(pa!=pb){
            pa = (pa != null?pa.next:headB);
            pb = (pb != null?pb.next:headA);
        }
        return pa;
    }
}

在最坏的情况下，只需要对两个链表都遍历一次，算法的时间复杂度为O(m+n)，空间复杂度为O(1)