Linked List: Given 2 LL, find the first common element

Problem Statement:

You are given 2 LL, you need to find the first common element between the given linked list.

Example:

List 1: 1 -> 4 -> 5 -> 2

List 2: 6 -> 7 -> 1 -> 2

Output 1

Solution Explanation:

For every node in the first list, search the second list.

Time Complexity: O(M * N)
Space Complexity: O(1)

Code Solution

#include <iostream> 
using namespace std;

class Node 
{ 
    public:
    int data; 
    Node *next;

    Node (int new_value)
    {
        data = new_value;
        next = nullptr;
    }
}; 

void print_list(Node *head) 
{ 
    Node *curr = head; 
    if(head != nullptr) 
    { 
        do 
        { 
        cout << curr->data << " "; 
        curr = curr->next; 
        } while(curr != head); 
      	cout << endl; 
    } 
} 

int solution(Node* headA, Node* headB)
{
    
    for (; headA != NULL; headA = headA->next)
	{ 
       for (Node *p = headB; p != NULL; p = p->next)
            if (p->data == headA->data)
                return headA->data;
 	}
    return -1;
}

int main() 
{ 
    // Created linked list will be 1 -> 4 -> 5 -> 2 
    Node *headA = new Node(1); 
    headA->next = new Node(4);
    headA->next->next = new Node(5);
    headA->next->next->next = new Node(2);

    // Created linked list will be 6 -> 7 -> 1 -> 2 
    Node *headB = new Node(6); 
    headB->next = new Node(7);
    headB->next->next = new Node(1);
    headB->next->next->next = new Node(2);

    cout << solution(headA, headB);
    
    return 0; 
} 

Output

1