[数据结构与算法]LeetCode两个链表的第一个重合节点

剑指 Offer II 023. 两个链表的第一个重合节点

给定两个单链表的头节点 headA 和 headB ，找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

输入：intersectVal = 8, listA = [4,1,8,4,5], listB [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at ‘8’
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。 从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。 在 A 中，相交节点前有 2个节点；在 B 中，相交节点前有 3 个节点。

提示：

listA 中节点数目为 m
listB 中节点数目为 n
0 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]

来源：力扣（LeetCode）

题目关键的点就是：
当两个链表有相同的节点时，对于长链表，先走过比短链表多的节点数，相当于长短链表在走过相同的节点数就能遇到相同的那个节点；
但是节点不一定存在，因此就需要遍历一遍，如果最后没有找到相同节点，就返回null，找到了也就是长短链表节点相同的位置直接返回就好。
所以题目的关键就是先遍历两个链表，找出长短链表，以及长链表比短链表多出来的节点数。

当然在写代码的时候有好多细节需要注意，所以会出现没有考虑到导致出错的情况，由于本人写的是判断是否到末尾节点用的是la.next==null，所以需要注意：

（1）最终结束的条件，不应该是longnode.next=null时，应该是longnode=null时。

考虑如下：当headA=headB.next或者headB=headA.next，此时经过操作之后，longnode其实就是最后一个节点了，如果while的条件是longnode.next！=null，那么就无法进入while中进行判断，也就无法返回。

当将while的条件改动了之后，也就不用在while里面加上要判断longnode.next和shortnode.next是否相等了。（当然加上的话也没问题，加速判断返回）

（2）当两个长度相等时，要时刻判断有没有相同的节点，要是有的话就可以直接返回。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode sub,longnode,shortnode;
        ListNode la=headA;
        ListNode lb=headB;
         /** if(headA.next==headB)
            return headB;
        if(headB.next==headA)
            return headA;*/
        while(la.next!=null&&lb.next!=null){
            if(la==lb){
                return la;
            }
            la=la.next;
            lb=lb.next;
        }
        if(la==lb){
            return la;
        }
        else if(la.next==null){
            sub=lb;
            longnode = headB;
            shortnode = headA;
        }
        else 
        {
            sub=la;
            longnode = headA;
            shortnode = headB;
        }
        while(sub.next!=null){
            sub=sub.next;
            longnode = longnode.next;
        }
        while(longnode!=null){
            
            if(longnode==shortnode){
                return longnode;
            }
            /** if(longnode.next==shortnode.next)
             {
                return longnode.next;
            }*/
            longnode=longnode.next;
            shortnode=shortnode.next;
            
        }
        return null;

    }
}

sub就是记录差的节点数，当sub走到最后一个节点，longnode此时也就和shortnode相当于对齐。

附：参考博文

今天的题虽然简答单，但是做的很坎坷，有一些细节的地方没有注意到容易被忽视。