2 个单链表的第一个交集 - 时间和空间复杂度？

Question

我写的这个方法的时间和空间复杂度是多少，它返回两个单链表之间的第一个节点的交集（如果没有找到 null）？

public Node getFirstNodeWhichIntersects(Node node1, Node node2) {
    Node currentPtr1 = node1;
    Node currentPtr2 = node2;   
    Node firstNode = null;
      
    while (currentPtr1 != null) {
       currentPtr2 = node2;
       while (currentPtr2 != null) {
          if (currentPtr1 == currentPtr2) {
              return currentPtr1;
          }     
          currentPtr2 = currentPtr2.next;
       }
       currentPtr1 = currentPtr1.next;
    }
    return firstNode;
}

Answer 1

在最坏的情况下，两个列表的尾节点是共享的第一个节点。该算法只能通过测试 all 可能的节点对（一个来自第一个列表，一个来自另一个）来找到它。

所以这个算法的最差时间复杂度为 O(𝑛𝑚)，其中𝑛 和𝑚 是第一个和第二个链表中的节点数。请注意，这个问题的算法的时间复杂度为 O(𝑛+𝑚)。

空间复杂度是微不足道的：变量的数量是固定的，每个变量的内存占用是固定的，所以空间复杂度是 O(1)。