《ACM练习 链表排序 II 【WA】.docx》由会员分享，可在线阅读，更多相关《ACM练习 链表排序 II 【WA】.docx（4页珍藏版）》请在金锄头文库上搜索。
1、ACM练习 链表排序 II 【WA】注意：在OJ上提交时不要使用endl，可能会出问题。用n代替。描述已知1. 小 g 手里有一个链表。2. 小 g 希望手里的链表是按照单调非减的顺序排好的。3. 小 g 希望链表中值相同的节点在排完序后相对次序也不会改变。4. 小 g 很笨。聪明的你快来帮帮小 g，实现他的愿望。输入第一行为两个整数，分别为小 g 的链表中节点的个数 N (0 N 100000)，和第一个节点的编号 H (1 H N)。接下来的 N 行中，第 i (1 i N) 行包含两个整数，分别为编号为 i 的节点的值 Ai (-109 Ai 109) 和它的下一个节点的编号 Bi (0
2、 Bi N)。约定链表中最后一个节点的下一个节点的编号用 0 表示，且空链表第一个节点编号用 0 表示。输出第一行为一个整数，为排序后的链表中第一个节点的编号。接下来的 N 行中，第 i (1 i N) 行包含一个整数，为排序后的链表中编号 i 的节点的下一个节点的编号 Bi (0 Bi N)。样例输入3 22 33 11 0样例输出3201我的测试用例20 120 219 318 417 516 615 714 813 912 1011 1111 1211 1311 1411 1511 1611 1711 1811 1911 2011 0输出结果（是对的吧）10012345678111213
3、141516171819209代码只通过了自己的测试用例，没通过OJ#include#include#includeusing namespace std;class Nodepublic: int num; int value; int next;int mysort(Node a1, Node a2) return(a1.value total first; /空链表检测 if (total = 0) cout 0; return 0; /原链表 vector linklist; Node tNode; int i; for (i = 0; i tNode.value tNode.next
4、; tNode.next = 0;/此数据无用置零 linklist.push_back(tNode); /复制 vector resultlist(linklist); /排序 stable_sort(linklist.begin(), linklist.end(), mysort); /填写 int j; for (i = 0; i total; i+) resultlistlinklisti.num - 1.next = (i + 1 total ? linklisti + 1.num : 0); /输出 cout linklist0.num endl; for (i = 0; i total; i+) cout resultlisti.next n; cout endl; system(pause); return 0;
