架构师训练营 - 第八周 - 作业

/**
 * 两个单向链表是否在某个元素开始合并，找出该元素
 * 将单向链表转成数组，利用数组的随机访问从最后一个元素开始比较，直至两边元素不想等
 * 时间复杂度应该是O(min(m,n)+m+n),空间复杂度应该是O(m+n)
 */
public class TestApplication {
    public static void main(String[] args) {
        List<String> list1 = new LinkedList<>();
        list1.add("a");
        list1.add("b");
        list1.add("x");
        list1.add("y");
        list1.add("z");

        List<String> list2 = new LinkedList<>();
        list2.add("d");
        list2.add("e");
        list2.add("f");
        list2.add("x");
        list2.add("y");
        list2.add("z");

        //假设m<n
        int m=list1.size();
        int n=list2.size();

        //转数组
        List<String> array1 = new ArrayList<>(m);
        List<String> array2 = new ArrayList<>(n);
        list1.forEach(p -> array1.add(p));
        list2.forEach(p -> array2.add(p));


        //从两个数组的最后一个元素开始比较
        int idx;
        boolean existFlag=false;
        for(idx=m-1;idx>-1;idx--){
            if(array1.get(idx).equals(array2.get(idx+n-m))){
                existFlag=true;
            }else{
                break;
            }
        }

        if(existFlag) {
            System.out.println(array1.get(idx + 1));
        }
    }
}