架构师训练营W8-作业

本周题目如下

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

首先我对该题目表示疑惑，合并判断这个问题，我觉得比较模糊，合并的前提没有说明白，如果简单理解那么就是找两个链表中第一个相同元素的位置，然后从该位置合并两个链表，那就会出现新的问题，如果后续节点还是有相同元素怎么办？

先写伪代码

class Node{
  Node(var val){
    this.val=val;
  }
  val=null;
  next=null;
}
Node one=new Node("a");
one.next=new Node("b");
Node b=head.next;
b.next=new Node("c");

Node two=new Node("d");
two.next=new Node("e");
Node e=head.next;
e.next=new Node("f");
// 我这里暂时假定合并条件为两个链表中第一个相同元素向后合并
boolean merge(Node one,Node two){
    if(one.val==tow.val){
       print("找到合并点x"+one.val);
       return true;
    }
    Node o=one;
    Node t=two;
    while((o=o.next)!=null){
      // 重新初始化 t
      t=two;
      while((t=t.next)!=null){
         if(o.val==t.val){
             print("找到合并点x"+one.val);
            return true;
         }
      }
    }
  return false;
}

时间复杂度分析

• 最坏情况，为链表 m*n 时间复杂度,简化为O(n²)，既两个循环查找 x，x为外循环链表最后一个节点
• 最好情况，O(1)，既两个表头一致，直接找到 X
• 平均情况，为 O(logn)，既只需要循环一半左右就找到合并点 x