架构师训练营第八周作业

关注

发布于: 2020 年 07 月 29 日

有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，如下图所示的这样，也可能不合并。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。
请用（伪）代码描述算法，并给出时间复杂度和空间复杂度。
﻿
﻿
方法一：Brute Force
最直接的方式是双重for循环，针对第一个链表的每个节点A，循环第二个链表，看第二个链表上的节点是否等于节点A，如是，则找到合并点，如果双重循环结束还没有找到，则没有合并。由于是双重循环，假设两个链表的长度分别为m和n，则时间复杂度为O(m*n)
public class ListNode{
  private int val;
  private ListNode next;
  //constructor method, getter and setter
}
public ListNode findJoinedNode(ListNode p, ListNode q){
  if(p == null || q == null) return null;
  ListNode tempP = p, tempQ = q;
  while(tempP != null){
    while(tempQ != null){
      if(tempP == tempQ) return tempP;
      tempQ = tempQ.next;
    }
    tempP = temP.next;
  }
  return null;
}
﻿
方法二：将链表1存入一个set中，循环链表2，对于链表2的每个节点，判断是否在set中存在。这种方式每个链表只需要循环一次，故时间复杂度为O(m+n)。
public ListNode findJoinedNode(ListNode p, ListNode q){
  Set<ListNode> set = new HashSet<>();
  while(p != null) {
    set.add(p);
    p = p.next;
  }
  while(q != null) {
    if(set.contains(q)) return q;
    q = q.next;
  }
  return null;
}
﻿