架构师训练营第 8 周作业

 关注

发布于: 2020 年 07 月 29 日

题目有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，如下图所示的这样，也可能不合并。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。
请用（伪）代码描述算法，并给出时间复杂度和空间复杂度。
﻿
﻿
题解1：直接法拿到题目能想到的最直接的办法就是，把其中一个链表的元素挨个扔到一个哈希表中，然后再遍历另外一个链表，查找是否在哈希表中有重合的元素。
该题解的时间复杂度为：O(m+n), 空间复杂度为O(m)
伪代码如下:
Node getNode(Node h1, Node h2) {
  Node next = h1;
  HashSet set = new HashSet();
  do {
    if (next != null) {
      set.add(next);
    }
    next = next.next();
  } while(next != null);
  
  for (Node n = h2; n != null; n = h2.next) {
    if (set.contains(n)) {
      return n;
    }
  }
  return null;
}
﻿
题解2： 双指针法双指针法是解决链表问题时常用的方法，这里需要稍稍用点小技巧。同时从两个链表头开始遍历，如果遍历到最后一个元素时，则跳回第一个元素，直至刚好遍历到第一个相遇的节点
Node getNode(Node h1, Node h2) {
  Node n1 = h1;
  Node n2 = h2;
  
  while (true) {
    if (n1 == n2) {
      return n1;
    }
    n1 = n1.next() == null ? h1 : n1.next();
    n2 = n2.next() == null ? h2 : n2.next();
  }
}
﻿

发布于: 2020 年 07 月 29 日阅读数: 32

原文链接:【http://xie.infoq.cn/article/4b9008e52321fd1df5fbfbe97】。文章转载请联系作者。

Season

 关注

还未添加个人签名 2019.09.28 加入

还未添加个人简介

发布

暂无评论

架构师训练营第 8 周作业

题目

题解1：直接法

题解2： 双指针法

Season

评论

题解2：双指针法