Y形链表中的交点

Question

给定两个大小为N和M的单链表，编写一个程序来获得两个链表相交的点。对于给定的输入：3 1 23 6 91015 30正确的输出应该是：15我的输出-10请帮我找出我的代码中的错误

int intersectPoint(Node* head1, Node* head2)
{
unordered_set<Node*> list1;
int output;
while(head1->next!=NULL){
list1.insert(head1);
head1=head1->next;
}
while(list1.find(head2)!=list1.end()){
head2=head2->next;
}
output=head2->data;
return output;
// Your Code Here
}

您可以访问此链接以更好地了解问题点击此处

Answer 1

您可以使用链表长度的概念。在Y形中，若要使链接列表具有公共部分，它应该具有相同的长度。为此，我们将首先计算两个链表的长度，然后从较大的链表中减去多余的链表，得到相同大小的链表。现在我们可以逐个节点进行比较，得到共同的节点。上述逻辑的代码为-

int listLen(Node *head){
int len =0;
Node * temp =head;
while(temp!=NULL){
len++;
temp=temp->next;
}
return len;
}
int intersectPoint(Node* head1, Node* head2)
{
int len1 =listLen(head1), len2 = listLen(head2);
if(!len1 || !len2)
return -1;
Node *temp1 =head1, *temp2 = head2;
while(len1>len2){
len1--;
temp1=temp1->next;
}
while(len2>len1){
len2--;
temp2=temp2->next;
}
while(temp1 && temp2){
if(temp1== temp2)
return temp1->data;
temp1=temp1->next;
temp2=temp2->next;
}
return -1;
}