输入两个链表，找出它们的第一个公共节点

方法一：
先求出两个链表的长度，求出长度之差k，让较长链表先走k步，然后两个链表同时走，最后相遇即为公共节点。

public static ListNode  getIntersectionNode(ListNode headA,ListNode headB){
        if(headA == null || headB == null) {
            return null;
        }
        //永远指向最长的单链表
        ListNode pL = headA;
        //永远指向最短的单链表
        ListNode pS = headB;
        int lenA = 0;
        int lenB = 0;
        //分别求长度
        while (pL != null) {
            lenA++;
            pL = pL.next;
        }
        while (pS != null) {
            lenB++;
            pS = pS.next;
        }
        pL = headA;
        pS = headB;
        //求长度的差值
        int len = lenA-lenB;
        //如果是负数-》pL = headB;  pS = headA
        if(len < 0) {
            pL = headB;
            pS = headA;
            len = lenB-lenA;
        }
        //只需要让pL走len步就好了
        while (len > 0) {
            pL = pL.next;
            len--;
        }
        //走完len步之后  两个同时开始走
        //一直走 走到next值相同时 就是交点
        while (pL != pS && pL != null) {
            pL = pL.next;
            pS = pS.next;
        }
        if(pL == pS && pS != null) {
            return pL;
        }
        return null;
}

方法二：如果两个链表的长度是相等的，就可以用两个指针指向两个链表的头部，同时走，直到指向相等就是他们的第一个公共节点。问题是什么呢，现在两个链表长度是不相同的，所以需要让两个链表长度相同，假设链表A长度是a，链表B长度是b，a+b=b+a所以将两个链表长度加起来就是相同的。

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if(pHead1==null||pHead2==null){
            return null;
        }
        ListNode acur=pHead1;
        ListNode bcur=pHead2;
        while(acur!=bcur){
            acur=acur.next;
            bcur=bcur.next;
            if(acur!=bcur){
                if(acur==null){
                    acur=pHead2;
                }
                if(bcur==null){
                    bcur=pHead1;
                }
            }
        }
        return acur;
    }
}

最后

以上就是外向人生为你收集整理的输入两个链表，找出它们的第一个公共节点的全部内容，希望文章能够帮你解决输入两个链表，找出它们的第一个公共节点所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。