第八周课后作业



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

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





先计算两个链表的长度m、n，找到那个较长的链表（longList）

让 longList 的头指针向后移动 abs(m-n) 个节点；这样长、短链表就一样长了

然后挨个比较两个链表的头指针，如果一样则返回该节点；不一样则头指针分别往后移动一位

循环步骤 3，直到链表遍历结束



时间复杂度 O(n)



空间复杂度 O(1)

public boolean listMeet(LinkedList shorts, LinkedList longs){



int temp = longs.size() - shorts.size();



// 去掉长链表的头，让两个链表一样长

while (temp>0){

longs.remove(0);

temp --;

}



// 从头开始比较两个链表，看是否相同，相同点就是合并点

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

if(shorts.get(i).equals(longs.get(i))){



// 相遇点

LinkedList meetNode = (LinkedList)shorts.get(i);

return true;

}

}

// 没有共同点

return false;

}