A1032-Sharing

ac 思路：还是按数组存，然后遍历第一条链表，置flag为1，然后遍历第二条，若能找到flag为1的就是有公共的。
其实本质上都是一样的，注意遍历的思想

#include<bits/stdc++.h>
using namespace std;
const int maxn=100010;

struct Node
{
    int add,next;
    char data;
    int flag;
}node[maxn];

int main()
{
    int start1,start2,N;
    for(int i=0;i<maxn;i++)
        node[i].flag=0; 
    scanf("%d %d %d",&start1,&start2,&N);
    int address;
    int p;
    for(int i=0;i<N;i++)
    {
        scanf("%d ",&address);
        scanf("%c %d",&node[address].data,&node[address].next);
        node[address].add=address;
    }
    for(p=start1;p!=-1;p=node[p].next)
        node[p].flag=1;
    for(p=start2;p!=-1;p=node[p].next)
    {
        if(node[p].flag==1)
        {
            printf("%05d",node[p].add);
            break;
        }       
    }
    if(p==-1)
        printf("-1");   
    return 0;
 } 

没ac思路，鉴于1074的思想把我成功带偏，想的很复杂，但是有一个点过不去，想不通，思路是把两条链表都排出来，然后从后向前比较，显然很费劲。

#include<bits/stdc++.h>
using namespace std;
const int maxn=100010;

struct Node
{
    int add,next;
    char data;
    int order;
}node1[maxn],node2[maxn];
bool cmp(Node a,Node b)
{
    return a.order<b.order;
}
int main()
{
    int start1,start2,N;
    for(int i=0;i<maxn;i++)
    {
        node1[i].order=maxn;
        node2[i].order=maxn;
    }       
    scanf("%d %d %d",&start1,&start2,&N);
    int address;
    for(int i=0;i<N;i++)
    {
        scanf("%d ",&address);
        scanf("%c %d",&node1[address].data,&node1[address].next);
        node2[address].add=node1[address].add=address;
        node2[address].data=node1[address].data;
        node2[address].next=node1[address].next;
    }
    int link1=start1,link2=start2;
    int count1=0,count2=0;
    while(link1!=-1)
    {
        node1[link1].order=count1++;
        link1=node1[link1].next;
    } 
    while(link2!=-1)
    {
        node2[link2].order=count2++;
        link2=node2[link2].next;
    } 
    sort(node1,node1+maxn,cmp);
    sort(node2,node2+maxn,cmp);
    int n1=count1-1,n2=count2-1;
    int flag=0;
    while(n1>=0&&n2>=0)
    {
        if(node1[n1].add==node2[n2].add)
        {
            n1--;n2--;
            flag=1;
        }
        else
        {
            if(flag)    
                printf("%05d",node1[n1].next);
            else
                printf("-1");
            break;
        }       
    }
    if(n1==-1||n2==-1)
    {
        if(n1==-1)
            printf("%05d",start1);
        else
            printf("%05d",start2);      
    }
    return 0;
 }