剑指Offer（三十六）两个链表的第一个公共交点（Java版 )

妖狐艹你老母 2021-09-26 23:40 207阅读 0赞

# 一、题目描述 #

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

# 二、代码分析 #

/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/
    public class Solution {
        public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
           if (pHead1 == null||pHead2 == null) {
                return null;
            }
            int count1 = 0;
            //将第一个链表的头保存下来
            ListNode p1 = pHead1;
            while (p1!=null){
                p1 = p1.next;
                //统计链表1的数目
                count1++;
            }
            int count2 = 0;
            ////将第一个链表的头保存下来
            ListNode p2 = pHead2;
            while (p2!=null){
                //统计链表2的数目
                p2 = p2.next;
                count2++;
            }
            int flag = count1 - count2;
            //如果链表1的数目比链表2的数目多
            if (flag > 0){
                while (flag>0){
                    pHead1 = pHead1.next;
                    flag --;     //找到多出的最后一个元素
                }
                while (pHead1!=pHead2){
                    pHead1 = pHead1.next;
                    pHead2 = pHead2.next;
                }
                return pHead1;
            }
            if (flag <= 0){
                while (flag<0){
                    pHead2 = pHead2.next;
                    flag ++;
                }
                while (pHead1 != pHead2){
                    pHead2 = pHead2.next;
                    pHead1 = pHead1.next;
                }
                return pHead1;
            }
            return null;
        }
    }

运行结果：  
![这里写图片描述][70]

[70]: /images/20210923/afc8d91d649d481291c82e9c3d3a7083.png