First Node of the Intersection between 2 Singly Linked Lists - Time & Space Complexity?

Question

What is the time & space complexity of this method I wrote which returns the first node of the intersection between two singly linked lists (and if none found just 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

In the worst case the tail node of both lists is the first node that is shared. This algorithm will only find it by testing all possible pairs of nodes (one from the first list, one from the other).

So that gives this algorithm a worst time complexity of O(𝑛𝑚), where 𝑛 and 𝑚 are the number of nodes in the first and second linked list. Note that there are algorithms for this problem with a time complexity of O(𝑛+𝑚).

The space complexity is trivial: there are a constant number of variables, each with a constant memory footprint, so the space complexity is O(1).