学步园

有题目可以很容易的看出。

单链表 公共节点。必然最后一个节点相同，两个链表成Y字形

感觉的话，需要从后往前找，那么只有栈具有这个后进先出的性质。那么c++的stl库当然成为了首先选择的结构了，为了节省时间吧，

用c实现一个花费的时间太多了。

代码如下

#include "iostream"
#include "stack"
using namespace std;
typedef struct Node
{
	int data;
	struct Node *next;
}Lnode;

int main()
{
	int num=10;
	int i=0,data;
	Lnode *head,*head1,*p,*q,*insert,*ret;
	head=NULL;
	head1=NULL;
	for(i=0;i<10;i++)
	{
		scanf("%d",&data);
		if(head == NULL)
		{
			head =(Lnode *)calloc(1,sizeof(Lnode));
			head->data=data;
			head->next=NULL;
			p=head;
		}	
		else
		{
			q = (Lnode *)calloc(1,sizeof(Lnode));
			q->data=data;
			q->next=NULL;
			p->next=q;
			p=p->next;
		}
		if(i==5)
			insert=q;
	} 
	p=head;
	while(p)
	{
		printf("%d ",p->data);
		p=p->next;
	}
	putchar('\n');
	for(i=0;i<5;i++)
	{
		scanf("%d",&data);
		if(head1 == NULL)
		{
			head1 =(Lnode *)calloc(1,sizeof(Lnode));
			head1->data=data;
			head1->next=NULL;
			p=head1;
		}	
		else
		{
			q = (Lnode *)calloc(1,sizeof(Lnode));
			q->data=data;
			q->next=NULL;
			p->next=q;
			p=p->next;
		}
	}
	p->next=insert;
	p=head1;
	while(p)
	{
		printf("%d ",p->data);
		p=p->next;
	}
	putchar('\n');
	stack<Lnode *> myStack1;
	stack<Lnode *> myStack2;
	
	while(head)
	{
		myStack1.push(head);
		head=head->next;
	}
	while(head1)
	{
		myStack2.push(head1);
		head1=head1->next;
	}
	p=NULL;
	q=NULL;
	do{
		ret=p;
		p=(Lnode *)myStack1.top();
		q=(Lnode *)myStack2.top();
		myStack1.pop();
		myStack2.pop();
	}while(p==q);
	printf("%d ",ret->data);
	return 0;
}

当然我以上的代码 不是书中推荐的方法。

书中的方法是，既然两个链表最后一个相等，长度不等，那么我们把长的那一个走一部分节点 ，使两个节点长度一样长

然后再开始比不就行了吗