算法學習之路|連結清單元素分類

給定一個單連結清單，請編寫程式将連結清單元素進行分類排列，使得所有負值元素都排在非負值元素的前面，而[0, K]區間内的元素都排在大于K的元素前面。但每一類内部元素的順序是不能改變的。例如：給定連結清單為 18→7→-4→0→5→-6→10→11→-2，K為10，則輸出應該為 -4→-6→-2→7→0→5→10→18→11。

輸入格式：

每個輸入包含1個測試用例。每個測試用例第1行給出：第1個結點的位址；結點總個數，即正整數N (<= 105)；以及正整數K (<=1000)。結點的位址是5位非負整數，NULL位址用-1表示。

接下來有N行，每行格式為：

Address Data Next

其中Address是結點位址；Data是該結點儲存的資料，為[-105, 105]區間内的整數；Next是下一結點的位址。題目保證給出的連結清單不為空。

輸出格式：

對每個測試用例，按連結清單從頭到尾的順序輸出重排後的結果連結清單，其上每個結點占一行，格式與輸入相同。

輸入樣例：

00100 9 10

23333 10 27777

00000 0 99999

00100 18 12309

68237 -6 23333

33218 -4 00000

48652 -2 -1

99999 5 68237

27777 11 48652

12309 7 33218

輸出樣例：

33218 -4 68237

68237 -6 48652

48652 -2 12309

12309 7 00000

99999 5 23333

23333 10 00100

00100 18 27777

27777 11 -1

解題思路：

利用map.first模拟連結清單的位址，

建立一個結構體，作為map.second，

儲存連結清單的值已經連結清單的next位址。

map模拟出一個連結清單，然後依據題目的意思解題即可。

詳情如下：