מריה בוטוסוב

יש למצוא נקודת מפגש שלי 2 רשימות מקושרות

//solution 1
public Node getIntersection(Node headA, Node headB) {
    if(headA == null || headB == null) return null;
    Node a_pointer = headA;
    Node b_pointer = headB;
    while(a_pointer != b_pointer) {
        if(a_pointer == null)
            a_pointer = headB;
        else
            a_pointer = a_pointer.next;
        if(b_pointer == null)
            b_pointer = headA;
        else
            b_pointer = b_pointer.next;
    }
    return a_pointer;
}
 
//solution 2
int getNodesCount(Node node)
{
	Node current = node;
	int count = 0;
 
	while (current != null)
	{
		count++;
		current = current.next;
	}
	return count;
}
 
int getNode(Node head1, Node head2)
{
	int c1 = getNodesCount(head1);
	int c2 = getNodesCount(head2);
	int d;
 
	if (c1 > c2)
	{
		d = c1 - c2;
		return getIntesectionNode(d, head1, head2);
	}
	else
	{
		d = c2 - c1;
		return getIntesectionNode(d, head2, head1);
	}
}
 
int getIntesectionNode(int d, Node node1, Node node2)
{
	int i;
	Node current1 = node1;
	Node current2 = node2;
	for (i = 0; i < d; i++)
	{
		if (current1 == null)
		{
			return -1;
		}
		current1 = current1.next;
	}
	while (current1 != null && current2 != null)
	{
		if (current1.data == current2.data)
		{
			return current1.data;
		}
		current1 = current1.next;
		current2 = current2.next;
	}
	return -1;
}