有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，也可能不合并，如下图所示的这样。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。
请用代码（或伪代码）描述算法，并给出时间复杂度。
public class test {
public static void main(String[] args) { List<String> bigOne = new ArrayList<>(); bigOne.add("d"); bigOne.add("e"); bigOne.add("f"); bigOne.add("x"); bigOne.add("y"); bigOne.add("z");
List<String> smallOne = new ArrayList<>(); smallOne.add("a"); smallOne.add("b"); smallOne.add("x"); smallOne.add("y"); smallOne.add("z");
int bigOneSize = bigOne.size(); int smallOneSize = smallOne.size(); //下标 int smallOnePositin = 0; //合并点下标 int p = -1; String value = "";//循环bignone， 查找和smallone第一个相同点 for (int i = 0; i < bigOneSize; i++) { if (p > -1) { if (++smallOnePositin >= smallOneSize) { break; } if (smallOne.get(smallOnePositin).equals(bigOne.get(i))) { continue; } p = -1; } smallOnePositin = smallOne.indexOf(bigOne.get(i)); if (smallOnePositin > -1) { p = smallOnePositin; value = bigOne.get(i); } }
if (p > -1) { System.out.println("the merge position is " + p + " and the value is " + value);
} else { System.out.println("the two list can't be merged"); }
}
}
复制代码
the retsult
思路
查找链表 M 和链表 N 第一个相同元素位置，然后循环链表 M 后续元素和链表 N 里面元素进行比较,后续比较都相等则可以合并，否则不能合并，时间复杂度 O(m)。
总结
评论