L2-002 链表去重

Powered by:NEFU AB-IN

Link

• L2-002 链表去重 (25 分)
• • 题意
  • 思路
  • 代码

• 题意

  给定一个带整数键值的链表 L，你需要把其中绝对值重复的键值结点删掉。即对每个键值 K，只有第一个绝对值等于 K 的结点被保留。同时，所有被删除的结点须被保存在另一个链表上。例如给定 L 为 21→-15→-15→-7→15，你需要输出去重后的链表 21→-15→-7，还有被删除的链表 -15→15。

• 思路

  单链表的运用，已知头节点和各个节点的val和next，直接连起来遍历即可
  ps: 本身节点的next不一定是最后的next，在最后答案数组中的下一个数才是真正的next

• 代码

  /*
  * @Author: NEFU AB-IN
  * @Date: 2022-04-19 16:37:06
  * @FilePath: \ACM\GPLT\L2-002.CPP
  * @LastEditTime: 2022-04-20 20:17:37
  */
  #include 
  using namespace std;
  #define int long long
  #define MP make_pair
  #define SZ(X) ((int)(X).size())
  #define IOS                                                                                                            \
      ios::sync_with_stdio(false);                                                                                       \
      cin.tie(0);                                                                                                        \
      cout.tie(0);
  #define DEBUG(X) cout << #X << ": " << X << endl;
  typedef pair<int, int> PII;
  const int INF = 0x3f3f3f3f;
  
  const int N = 1e5 + 10;
  int h, e[N], ne[N], st[N];
  
  int n;
  signed main()
  {
      IOS;
      cin >> h >> n;
      for (int i = 1; i <= n; ++i)
      {
          int address, val, next;
          cin >> address >> val >> next;
          e[address] = val;
          ne[address] = next;
      }
  
      vector<int> v1, v2;
      for (int i = h; ~i; i = ne[i])
      {
          int val = e[i];
          if (st[abs(val)])
              v2.push_back(i);
          else
          {
              st[abs(val)] = 1;
              v1.push_back(i);
          }
      }
      for (int i = 0; i < SZ(v1); ++i)
      {
          printf("%05lld %lld ", v1[i], e[v1[i]]);
          if (i == SZ(v1) - 1)
              printf("-1\n");
          else
              printf("%05lld\n", v1[i + 1]);
      }
      for (int i = 0; i < SZ(v2); ++i)
      {
          printf("%05lld %lld ", v2[i], e[v2[i]]);
          if (i == SZ(v2) - 1)
              printf("-1\n");
          else
              printf("%05lld\n", v2[i + 1]);
      }
      return 0;
  }