注意：在OJ上提交時不要使用endl，可能會出問題。用\n代替。

描述

已知

小 g 手里有一個鏈表。

小 g 希望手里的鏈表是按照單調非減的順序排好的。

小 g 希望鏈表中值相同的節(jié)點在排完序后相對次序也不會改變。

小 g 很笨。

聰明的你快來幫幫小 g，實現他的愿望。

輸入
第一行為兩個整數，分別為小 g 的鏈表中節(jié)點的個數 N (0 ≤ N ≤ 100000)，和第一個節(jié)點的編號 H (1 ≤ H ≤ N)。
接下來的 N 行中，第 i (1 ≤ i ≤ N) 行包含兩個整數，分別為編號為 i 的節(jié)點的值 Ai (-10^9 ≤ Ai ≤ 10^9) 和它的下一個節(jié)點的編號 Bi (0 ≤ Bi ≤ N)。

約定鏈表中最后一個節(jié)點的下一個節(jié)點的編號用 0 表示，且空鏈表第一個節(jié)點編號用 0 表示。

輸出
第一行為一個整數，為排序后的鏈表中第一個節(jié)點的編號。
接下來的 N 行中，第 i (1 ≤ i ≤ N) 行包含一個整數，為排序后的鏈表中編號 i 的節(jié)點的下一個節(jié)點的編號 Bi’ (0 ≤ Bi’ ≤ N)。

樣例輸入
3 2
2 3
3 1
1 0

樣例輸出
3
2
0
1
我的測試用例

20 1
20 2
19 3
18 4
17 5
16 6
15 7
14 8
13 9
12 10
11 11
11 12
11 13
11 14
11 15
11 16
11 17
11 18
11 19
11 20
11 0

輸出結果（是對的吧）

10
0
1
2
3
4
5
6
7
8
11
12
13
14
15
16
17
18
19
20
9

代碼

只通過了自己的測試用例，沒通過OJ

#include<iostream> #include<vector> #include<algorithm> using namespace std; class Node { public:int num;int value;int next; };int mysort(Node a1, Node a2) {return(a1.value < a2.value); }int main() {int total, first;cin >> total >> first;//空鏈表檢測if (total == 0){cout << '0';return 0;}//原鏈表vector<Node> linklist;Node tNode;int i;for (i = 0; i < total; i++){tNode.num = i + 1;cin >> tNode.value >> tNode.next;tNode.next = 0;//此數據無用置零linklist.push_back(tNode);}//復制vector<Node> resultlist(linklist);//排序stable_sort(linklist.begin(), linklist.end(), mysort);//填寫int j;for (i = 0; i < total; i++){resultlist[linklist[i].num - 1].next = (i + 1 < total ? linklist[i + 1].num : 0);}//輸出cout << linklist[0].num << endl;for (i = 0; i < total; i++){cout << resultlist[i].next << '\n';}cout << endl;system("pause");return 0; }

總結

以上是生活随笔為你收集整理的ACM练习 链表排序 II 【WA】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。