week8 作业 1

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

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





分析：由于是单向链表，如果这两个单向链表在某个元素合并，则这个合并的元素后的每个元素都是合并的。



伪代码如下：

由于已知这两个链表的长度，则可以判断出两个链表的长短，假设这两个链表分表为L1和L2，长度分别为m和n，定义两个指针p1和p2

if L1为空或L2为空：

return NULL

if m >= n：

p1 指向L1的头结点

p2指向L2的头结点

else:

p1指向L2的头结点

p2指向L1的头结点



diff = abs(m - n)

遍历长链表的前diff步

for(int i=0; i<diff; i++){

p1 = p1->next;

}

遍历后续的链表节点

while(p1 != p2)

{

p1 = p1->next;

p2 = p2->next

}

返回p1

时间复杂度：o(n+m)

空间复杂度：o(1)