链接

试题链接
解题报告备份链接

解题思路

这是一道模拟题。要求不断地让一个列表追加到另一个列表中，并反转。但是不停反转是很耗性能的，不停地反转将会导致超时。为了解决这个反转超时问题，我们开两个表，一个正向表，一个反向表。把正向表与反向表的元素对调一下，就相当于反转了。这样就不会超时了。

      +-----------+
      |   开始    |
      +-----------+
             |
             |
             |
             |
             v
+---------------------------------+
| 建两个链表，一个正向表，一个反向表 |
+---------------------------------+
             |
             |<-------------------------------+
             |                                |
             v                                |
     +-------------+                          |
     | 输入追加操作 |                          |
     +-------------+                          |
             |                                |
             |                                |
             |                                |
             v                                |
    +------------------------+                |
    | 对正向表执行追加操作，即 |                |
    | 正向表La += Lb         |                |
    +------------------------+                |
             |                                |
             |                                |
             |                                |
             v                                |
   +---------------------------------+        |
   | 对反向表倒过来执行逆向追加操作，即 |        |
   | 反向表Lb += La                  |        |
   +---------------------------------+        |
             |                                |
             |                                |
             |                                |
             v                                |
   +-------------------------------------+    |
   | 把这两个表的刚变的两个元素对调一下，即 |    |
   | swap(正La, 反Lb)                    |    |
   +-------------------------------------+    |
              |                               |
              |                               |
              v                               |
   +-------------------------------+          |
   | 把反向表的元素放到正确的位置，即 |          |
   | swap(反La, 反Lb)              |          |
   +-------------------------------+          |
              |                               |
              |                               |
              |                               |
              v                               |
              X                               |
            X XXX                             |
         XXX     XXX                          |
      XXXX          XXXX     有               |
   XXXX 还有下个操作吗？  XX+------------------+
 XX                    XXX
 XX XXX               XX
       XXXXXX       XX
            XXXX X X
              XX
               |
               |  无
               |
               v
      +-------------------+
      |                   |
      | 输出正向表的L1元素 |
      |                   |
      +-------------------+
               |
               |
               |
               |
               |
               v
          +---------+
          |   结束  |
          +---------+

源代码

#include <cstdio>
#include <list>
#include <algorithm>

using namespace std;

#define MAX_LENGTH 100001

int main()
{
    int n, m;
    static list<int> plist[MAX_LENGTH];
    static list<int> plist_reverse[MAX_LENGTH];
    while (scanf("%d%d", &n, &m) != EOF)
    {
        for (int i = 1; i <= n; ++i)
        {
            plist[i].clear();
            plist[i].push_back(i);

            plist_reverse[i].clear();
            plist_reverse[i].push_back(i);
        }
        while (m --)
        {
            int a, b;
            scanf("%d%d", &a, &b);
            plist[a].splice(plist[a].end(), plist[b]);
            plist_reverse[b].splice(plist_reverse[b].end(), plist_reverse[a]);
            swap(plist[a], plist_reverse[b]);
            swap(plist_reverse[a], plist_reverse[b]);
        }
        printf("%d", (int)(plist[1].size()));
        for (int e : plist[1])
            printf(" %d", e);
        puts("");
    }
    return 0;
}