1.链表反转

描述

输入一系列有向边，判断其是否构成一个单向链表。若构成单向链表，则输出该单向链表的反向形式。若不构成，输出NO。

格式

输入：
每行为一条有向边src dst，以空格分隔出发点和到达点。src和dst可能为字符串，输入以EOF结束。
输出：
情况1：每行一个点名，输出该单向链表的反向形式。
情况2：NO

样例

输入1

个 一
是 这
句 个
。 子
一 是
子 句

输出1

这
是
一
个
句
子
。

输入2

1 2
3 2

输出2

NO

题解

#include<iostream>
#include<string>
#include <sstream>
using namespace std;
bool IsLink(string, int);
typedef struct Node {
    string data;
    struct Node *next;
    int flag = 0;
}Node,*Link;
Node node[2000];
int main()
{
    string a, b, c;
    int i = 1;
    while (getline(cin, c))
    {
        //以空格分割字符串
        istringstream is(c);
        is >> a >> b;
        //每输入一条边以两个节点存储。如果某点有两个入度，输出NO，说明不为链表但可能为环。
        if (IsLink(b,i-1))
        {
            node[(i++)-1].data = a;
            node[(i++)-1].data = b;
            node[i - 2].next = &node[i - 3];
            node[i - 3].flag = 2;
        }
        else 
        {
            cout << "NO" << endl;
            return 0;
        }
    }
    i--;

    //Link L = (Link)malloc(sizeof(Node)*2000);这里还不熟悉链表使用
    Node *head= (Node *)malloc(sizeof(Node));
    Node *k= (Node *)malloc(sizeof(Node));
    bool isHoop = true;

    //找到“头”结点，是一个没有被指向的节点。
    for (int j = 0; j < i; j+=2)
    {
        for (int m = 1; m < i ; m += 2)
        {
            if (node[j].data == node[m].data)
            {
                node[j].flag = 1;
                node[m].flag = 1;
            }
        }
    }

    /*//看一下是否找到头结点
    for (int j = 0; j<i; j++)
        if (node[j].flag == 0)
            cout << node[j].data;*/

    //k指向要输出的第一个字符，即头结点的下一个节点
    for (int j = 0; j < i; j++) 
        if (node[j].flag == 0)
        {
            head->next = &node[j];
            k = head->next->next;
            isHoop = false;
        }

    //如果是环，结束。
    if (isHoop)
    {
        cout << "NO" << endl;
        return 0;
    }

    //尾插法连成输出链表
    for (int m = 0;m<i/2+1;m++)
    {
        //cout << "here"<<i;
        for (int j = 1; j < i; j += 2) 
        {
            if (k->data == node[j].data)
            {
                //cout << "here2";
                Node *tmp= (Node *)malloc(sizeof(Node));
                tmp = node[j].next;
                k->next = tmp;
                k = k->next;
                break;
            }
        }
    }

    //找到要输出的最后一个字符，标识为2.
    for (int j = 0; j<i; j++)
        if (node[j].flag == 2)
        {
            Node *tmp = (Node *)malloc(sizeof(Node));
            tmp = &node[j];
            k->next = tmp;
            k = k->next;
        }

    k = head->next;//令k指向首节点
    //输出
    for (int j = 0; j < (i / 2+1); j++)
    {
        cout << k->data << endl;
        if (k->next != NULL)
        {
            k = k->next;
        }
    }
    return 0;
}

//判断是否为链表
bool IsLink(string b, int i) 
{
    bool flag = true;
    for (int j = 1; j < i; j+=2)
        if (node[j].data == b)
            flag = false;
    return flag;
}