第八周课后练习



有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，也可能不合并，如下图所示的这样。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。

请用代码（或伪代码）描述算法，并给出时间复杂度。



public class TT {



public static void main(String[] args) {



List<Integer> tl1 = new ArrayList();

tl1.add(1);

tl1.add(2);

tl1.add(3);

tl1.add(4);

tl1.add(5);



List<Integer> tl2 = new ArrayList();

tl2.add(6);

tl2.add(7);

tl2.add(8);

tl2.add(0);



List<Integer> tl3 = new ArrayList();

tl3.add(3);

tl3.add(4);

tl3.add(5);



List<Integer> tl4 = new ArrayList();

tl4.add(2);

tl4.add(3);

tl4.add(4);

tl4.add(5);

tl4.add(6);



merge(tl1,tl2);//链表不会合并

merge(tl1,tl3);//链表可以合并，合并位置元素 为3

merge(tl1,tl4);//链表可以合并，合并位置元素 为2

merge(tl3,tl4);//链表可以合并，合并位置元素 为3



}



public static void merge(List<Integer> tl1,List<Integer> tl2){

List<Integer> l1 = minSizeList(tl1,tl2);

List<Integer> l2 = maxSizeList(tl1,tl2);



int r = mergeWhere(l1,l2);

if( r > -1 ){

System.out.println("链表可以合并，合并位置元素 为"+l2.get(r));

}else {

System.out.println("链表不会合并");

}



}



/**

*

* @param l1 长度较短的链表

* @param l2 较长的链表

* @return 长链表中开始合并的位置下标

*/

public static int mergeWhere(List<Integer> l1,List<Integer> l2){

if( l1.size() > l2.size() ){

throw new IllegalArgumentException("传入参数错误");

}



/* l2 当前正在匹配位置,游标 /

int p = 0;

/* l2 开始合并的位置下标 /

int r = -1;



for (int i=0;i<l1.size();i++){

if( r > -1 ){

if( ++p >= l2.size() ){

break;

}

if( l2.get(p).equals(l1.get(i)) ){

continue;

}

r = resetPosition();

}

if( (p = l2.indexOf(l1.get(i))) > -1 ){

r=p;

continue;

}

}

return r;

}



private static int resetPosition() {

return -1;

}



private static List<Integer> maxSizeList(List<Integer> tl1, List<Integer> tl2) {

return tl1.size()>tl2.size()?tl1:tl2;

}



private static List<Integer> minSizeList(List<Integer> tl1, List<Integer> tl2) {

return tl1.size()<=tl2.size()?tl1:tl2;

}



}