从两个相交的链表中查找相交节点

6 回答

• 7

  这需要O（M N）时间和O（1）空间，其中M和N是链表的总长度 . 如果公共部分很长（即M，N >> m，n）可能效率低下

  • 遍历两个链表以找到M和N.

  • 回到头部，然后遍历| M - N |较长列表上的节点 .

  • 现在进入锁定步骤并比较节点，直到找到常见节点 .

  ---

  编辑：见http://richardhartersworld.com/cri/2008/linkedlist.html

  回复于 2024-04-24T04:04:35+08:00
• 0

  如果可能，您可以添加“颜色”字段或类似于节点 . 迭代其中一个列表，随时为节点着色 . 然后迭代第二个列表 . 一旦到达已经着色的节点，就会找到交叉点 .

  回复于 2024-04-24T04:04:35+08:00
• 0

  将两个列表的内容（或地址）转储到一个哈希表中 . 第一次碰撞是你的交集 .

  回复于 2024-04-24T04:04:35+08:00
• 46

  检查每个列表的最后一个节点，如果有一个交叉点，它们的最后一个节点将是相同的 .

  回复于 2024-04-24T04:04:35+08:00
• 16

  这是我在深夜编码时发现的疯狂解决方案，它比接受的答案慢2倍但使用了一个很好的算术黑客：

  public ListNode findIntersection(ListNode a, ListNode b) {
      if (a == null || b == null)
          return null;
  
      int A = a.count();
      int B = b.count();
  
      ListNode reversedB = b.reverse();
  
      // L = a elements + 1 c element + b elements
      int L = a.count();
  
      // restore b
      reversedB.reverse();
  
      // A = a + c
      // B = b + c
      // L = a + b + 1
  
      int cIndex = ((A+B) - (L-1)) / 2;
      return a.atIndex(A - cIndex);
  }
  

  我们将列表拆分为三个部分： a 这是第一个列表的一部分，直到公共部分开始， b 这是第二个列表的一部分，直到公共部分和 c 这是两个列表的共同部分 . 我们计算列表大小然后反向列表 b ，这将导致当我们从 a 开始遍历列表时，我们将在 reversedB 结束（我们将返回 a -> firstElementOfC -> reversedB ） . 这将为我们提供三个方程式，使我们可以获得公共部分的长度 c .

  这对于编程比赛或在制作中使用来说太慢了，但我认为这种方法很有趣 .

  回复于 2024-04-24T04:04:35+08:00
• 1

  也许在这一点上无关紧要，但这是我的脏递归方法 . 这需要 O(M) 时间和 O(M) 空间，其中 M >= N 为 list_M 长度 M 和 list_N 长度 N

  • 递归迭代到两个列表的末尾，然后从步骤 2 开始计数 . 请注意 list_N 将在 list_M 之前命中 null ，因为 M > N

  • 相同长度 M=N 在 list_M != list_N && list_M.next == list_N.next 时相交

  • 不同长度 M>N 在 list_N != null 时相交

  代码示例：

  Node yListsHelper(Node n1, Node n2, Node result) {
      if (n1 == null && n2 == null)
          return null;
      yLists(n1 == null ? n1 : n1.next, n2 == null ? n2 : n2.next, result);
      if (n1 != null && n2 != null) {
          if (n2.next == null) { // n1 > n2
              result.next = n1;
          } else if (n1.next == null) { // n1 < n2
              result.next = n2;
          } else if (n1 != n2 && n1.next == n2.next) { // n1 = n2
              result.next = n1.next; // or n2.next
          }
      }
      return result.next;
  }
  

  回复于 2024-04-24T04:04:35+08:00