/* 一个形如"Y"的链表 求其交点 */
#include <iostream> #include <stack> using namespace std;
typedef struct node{ int value ; struct node *next; }List; /*创建链表*/ void Create(List* &Head ,List* &End,int arr[],int Count) { if(Count<=0) return ; int nodevalue = 0; List *node= NULL; for(int i=0;i<Count;i++){ nodevalue = arr[i]; node =new List; node->value = nodevalue; node->next = NULL; if(Head == NULL){ Head = node; } else{ End->next = node; } End = node; } } /*遍历链表*/ void Traval(List* Head,List* End){ if(Head == NULL || End == NULL) return ; List* ptr = Head; while(ptr != End){ cout<<ptr->value<<" "; ptr= ptr->next; } cout<<endl; } /*查找交点*/ void FindNodeValue(List* Head_1,List* End_1,List* Head_2,List* End_2,int &Result) { if(Head_1 == NULL || End_1 == NULL || Head_2 == NULL || End_2 == NULL) return ; stack<List*> stack_1,stack_2; List* ptr = NULL; ptr= Head_1; while(ptr != End_1){ stack_1.push(ptr); ptr=ptr->next; } ptr = Head_2; while(ptr != End_2){ stack_2.push(ptr); ptr=ptr->next; } ptr = stack_1.top(); stack_1.pop(); List* ptr_1 = stack_2.top(); stack_2.pop(); List* re = NULL; while(ptr == ptr_1){ re = ptr; ptr = stack_1.top(); stack_1.pop(); ptr_1 = stack_2.top(); stack_2.pop(); } Result = re->value; } int main(){ int arr[] = {3,4,2,4,2,4,3,7}; List *Head_1=NULL,*End_1=NULL,*Head_2=NULL,*End_2=NULL; Create(Head_1,End_1,arr,sizeof(arr)/sizeof(int)); int arr_1[]= {4,3,5,6,5}; Create(Head_2,End_2,arr_1,sizeof(arr_1)/sizeof(int)); int Count = 3; List* ptr = Head_1; while(Count > 0){ ptr= ptr->next; Count--; } End_2->next = ptr; //cout<<ptr->value<<"\t"<<ptr->next->value<<endl; ptr = End_2; while(ptr->next != NULL){ ptr=ptr->next; } End_2= ptr; Traval(Head_1,End_1); Traval(Head_2,End_2); int Result =0; FindNodeValue(Head_1,End_1,Head_2,End_2,Result); cout<<Result<<endl; system("pause"); return 0; }
