【面试题36-两个链表的第一个公共结点】

剑指offer第三十六题。

题目描述

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

解题思路

这个题目的两个链表应该是有共同的尾部，而不是简单的交叉。对于这种性质，可能有更好的思路，但是我这里还是用了比较简单的想法，遍历第一个链表放进set中，再遍历另一个链表，找到第一个一样的结点，就是公共结点。时间复杂度为O(m+n)

我的答案

import java.util.HashSet;
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
         if(pHead1 == null || pHead2 == null){
             return null;
         }
        
        HashSet<ListNode> set = new HashSet<>();
        
        while(pHead1 != null){
            set.add(pHead1);
            pHead1 = pHead1.next;
        }
        
        while(pHead2 != null){
            if(set.contains(pHead2)){
                return pHead2;
            }
            pHead2 = pHead2.next;
        }
        
        return null;
    }
}