1025 反轉鏈表

一、題目

給定一個常數 K 以及一個單鏈表 L，請撰寫程式將 L 中每 K 個結點反轉，例如：給定 L 為 1→2→3→4→5→6，K 為 3，則輸出應該為 3→2→1→6→5→4；如果 K 為 4，則輸出應該為 4→3→2→1→5→6，即最后不到 K 個元素不反轉，

二、輸入輸出

輸入格式

每個輸入包含 1 個測驗用例，每個測驗用例第 1 行給出第 1 個結點的地址、結點總個數正整數 N ( ≤ 1 0 5 ≤10^5 ≤105?? )、以及正整數 K ( ≤ N ≤N ≤N)，即要求反轉的子鏈結點的個數，結點的地址是 5 位非負整數，NULL 地址用 ?1 表示，

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

Address Data Next

其中 Address 是結點地址，Data 是該結點保存的整數資料，Next 是下一結點的地址，

輸出格式

對每個測驗用例，順序輸出反轉后的鏈表，其上每個結點占一行，格式與輸入相同，

三、樣例

輸入樣例

00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

輸出樣例

00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1

四、題目分析

首先讀入資料存入unordered_map,從頭節點開始依次找到所有有效節點，存入向量，遍歷向量，節點進入雙端佇列，每滿k個，逆序存放人新的向量，最后未滿k個的節點正序存放，按照格式輸出lists向量，

五、代碼

#include <bits/stdc++.h>
using namespace std;
struct node
{
    int address;
    int value;
    int next;
};
struct no
{
    int address;
    int value;
};
vector<node> nodes;
unordered_map<int, node> ump;
deque<node> deq;
vector<no> lists;
int main()
{
    int first_address;
    int node_num;
    int k;

    cin >> first_address >> node_num >> k;
    for (int i = 0; i < node_num; i++)
    {
        node n;
        cin >> n.address >> n.value >> n.next;
        ump.insert(pair<int, node>(n.address, n));
    }
    node n;
    n.address = first_address;
    n.value = ump[first_address].value;
    n.next = ump[first_address].next;
    nodes.push_back(n);
    while (n.next != -1)
    {
        n.address = n.next;
        n.value = ump[n.address].value;
        n.next = ump[n.address].next;
        nodes.push_back(n);
    }
    ump.clear();
    for (int i = 0; i < nodes.size();)
    {
        for (int j = 0; j < k; j++)
        {
            node x = nodes[i];
            deq.push_back(x);
            i++;
            if (i == nodes.size())
                break;
        }
        if (deq.size() == k)
        {
            while (deq.size() != 0)
            {
                no y;
                y.address = deq.back().address;
                y.value = deq.back().value;
                lists.push_back(y);
                deq.pop_back();
            }
        }
    }
    while (deq.size() < k && deq.size())
    {
        no y;
        y.address = deq.front().address;
        y.value = deq.front().value;
        lists.push_back(y);
        deq.pop_front();
    }
    for (int i = 0; i < lists.size(); i++)
    {
        if (!i)
        {
            printf("%05d %d ", lists[i].address, lists[i].value);
        }
        else
        {
            printf("%05d\n%05d %d ", lists[i].address, lists[i].address, lists[i].value);
        }
    }
    printf("-1");
    return 0;
}

六、總結

unordered_map
頭檔案： #include < unordered_map >
unordered_map內部實作了一個哈希表（也叫散串列，通過把關鍵碼值映射到Hash表中一個位置來訪問記錄，查找的時間復雜度可達到O(1)，其在海量資料處理中有著廣泛應用），因此，其元素的排列順序是無序的，