第八周作业 (作业一)

关注

发布于: 2020 年 11 月 15 日

有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，也可能不合并，如下图所示的这样。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。
请用代码（或伪代码）描述算法，并给出时间复杂度。
﻿
﻿
public Node getCombineNode(LinkedList list1, LinkedList list2){
        Node retnode = null;
        if(null == list1 || null == list2) return retnode;
        Set<Node> map = new HashSet<>();
        int list1len = list1.size();
        int list2len = list2.size();
        int len = list1len > list2len ? list1len : list2len;
        for (int i = 0; i < len; i++) {             
            if(i >= list1len) break;
            if(i >= list2len) break;
            Node list1temp = (Node)list1.get(i);
            if(map.contains(list1temp)){
                retnode = list1temp;
                break;
            }
            map.add(list1temp);
            Node list2temp = (Node)list2.get(i);
            if(map.contains(list2temp)){
                retnode = list2temp;
                break;
            }
            map.add(list2temp);
        }
        return retnode;
    }
我这里采用了java，然后里面用到了数组链表,时间复杂度为O(n),空间复杂度为O(n)