输入2个链表，找出这2个链表当中的第1个公共结点应该如何实现呢?下面给大家整理了Java实现实例和思路。

题目：

输入2个链表，找出2个链表中第1个公共结点

注：

因为传入数据是链表，所以，误测试数据的提示是用其他方式显示的，保证传入数据是正确的。

思路1：

首先，要找出两个链表的长度，之后再让长的先走2个链表的长度差，随后再一起走，因为两个链表用公共的尾部。

代码实现：

class Solution
{
    public:
        ListNode * FindFirstCommonNode(ListNode * pHead1, ListNode * pHead2)
        {
            int len1 = findListLenth(pHead1);
            int len2 = findListLenth(pHead2);
            if (len1 > len2)
            {
                pHead1 = walkStep(pHead1, len1 - len2);
            }
            else
            {
                pHead2 = walkStep(pHead2, len2 - len1);
            }
            while (pHead1 != NULL)
            {
                if (pHead1 == pHead2) return pHead1;
                pHead1 = pHead1 - > next;
                pHead2 = pHead2 - > next;
            }
            return NULL;
        }
    int findListLenth(ListNode * pHead1)
    {
        if (pHead1 == NULL) return 0;
        int sum = 1;
        while (pHead1 = pHead1 - > next) sum++;
        return sum;
    }
    ListNode * walkStep(ListNode * pHead1, int step)
    {
        while (step--)
        {
            pHead1 = pHead1 - > next;
        }
        return pHead1;
    }
};

思路2：(思路清晰，代码易懂)

代码实现：

class Solution
{
    public:
        ListNode * FindFirstCommonNode(ListNode * pHead1, ListNode * pHead2)
        {
            /*
             假定 List1长度: a+n  List2 长度:b+n, 且 a<b
             那么 p1 会先到链表尾部, 这时p2 走到 a+n位置,将p1换成List2头部
             接着p2 再走b+n-(n+a) =b-a 步到链表尾部,这时p1也走到List2的b-a位置，还差a步就到可能的第一个公共节点。
             将p2 换成 List1头部，p2走a步也到可能的第一个公共节点。如果恰好p1==p2,那么p1就是第一个公共节点。  
             或者p1和p2一起走n步到达列表尾部，二者没有公共节点，退出循环。同理a>=b.
             时间复杂度O(n+a+b) 
            */
            ListNode * p1 = pHead1;
            ListNode * p2 = pHead2;
            while (p1 != p2)
            {
                if (p1 != NULL) p1 = p1 - > next;
                if (p2 != NULL) p2 = p2 - > next;
                if (p1 != p2)
                {
                    if (p1 == NULL) p1 = pHead2;
                    if (p2 == NULL) p2 = pHead1;
                }
            }
            return p1;
        }
};

思路3：

运用HasnMap的特性。

代码实现：

import java.util.HashMap;
public class Solution
{
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2)
    {
        ListNode current1 = pHead1;
        ListNode current2 = pHead2;
        HashMap < ListNode, Integer > hashMap = new HashMap < ListNode, Integer > ();
        while (current1 != null)
        {
            hashMap.put(current1, null);
            current1 = current1.next;
        }
        while (current2 != null)
        {
            if (hashMap.containsKey(current2))
                return current2;
            current2 = current2.next;
        }
        return null;
    }
}

根据以上的3种代码实例和思路相信你也应该有自己的想法了，赶紧动手写起来吧!更多Java实例，可以继续来本站了解哦。