1074 Reversing Linked List (25分)[靜态連結清單]

By Jalan

文章目錄

• **By Jalan**
• 知識工具需求
• • 數學
  • 資料結構和算法
  • 語言
• 題幹
• • 輸入條件
  • • 例1
  • 輸出條件
  • • 例1
• 題解
• • 第一次
  • • 思路
    • 預期時間複雜度
    • 編寫用時
    • 代碼
    • • CPP
      • • 運作用時
• 結尾

知識工具需求

數學

資料結構和算法

• 連結清單
• 棧

語言

• 可以通過%05d這種格式來進行前補零共5位(可超不少)的格式化輸出

題幹

給一個連結清單L和一個常數K,每K個數字反轉連結清單,比如

L being 1→2→3→4→5→6, if K3輸出3→2→1→6→5→4;

if K4, 輸出 4→3→2→1→5→6.

輸入條件

第一行包含:第一個節點的位址(5位非負),節點總數N[0,10^5],正整數K<=N是反轉長.NULL是-1

下面是N行

Address Data Next

例1

00100 6 4

00000 4 99999

00100 1 12309

68237 6 -1

33218 3 00000

99999 5 68237

12309 2 33218

輸出條件

輸出反轉之後的連結清單

例1

00000 4 33218

33218 3 12309

12309 2 00100

00100 1 99999

99999 5 68237

68237 6 -1

題解

第一次

思路

注意題目裡的反轉實際上操作的是next,每個節點的address和key實際上是不變的,隻要把反轉之後的元素排好然後把i的next設定成i+1的id就行.末尾不滿K個的是不反轉的

首先申請一個大數組存放靜态連結清單.

每K個一組周遊這個連結清單

(通過下面兩步實作反轉)

申請一個棧,每K個存到棧裡,

出棧所有元素到一個resultList裡.

把末尾不足K的不經過棧直接放到resultList裡

把resultList第i個的next變成i+1的id(也可以在輸出的時候每行第三個輸出i+1的id)

控制輸出最後一個.

預期時間複雜度

nlogn

編寫用時

30分鐘

代碼

CPP

#include <stack>
#include <stdio.h>
#include <vector>
using namespace std;

typedef struct node
{
    int id;
    int key;
    int next;
} node;

int main(int argc, char const *argv[])
{
    //input
    int nowId, N, K;
    scanf("%d%d%d", &nowId, &N, &K);
    vector<node> linkedList(100001);
    for (int i = 0, tempId, tempKey, tempNext; i < N; i++)
    {
        scanf("%d%d%d", &tempId, &tempKey, &tempNext);
        linkedList[tempId].id = tempId;
        linkedList[tempId].key = tempKey;
        linkedList[tempId].next = tempNext;
    }

    //process
    vector<node> resultList;
    stack<node> s;
    if (nowId == -1)
    {
        return 0;
    }
    else
    {
        while (nowId != -1) //這裡面也可以是1反正隻有一個出口
        {
        	//從nowId向前查找K個看能不能找到.
            int Kcounter = 0;
            int nowIdPlusK = nowId;
            if (nowId != -1)
            {
                ++Kcounter;
                nowIdPlusK = linkedList[nowId].next;
            }
            for (int i = 0; i < K - 1; i++)//好像寫重了,改成K把前面那個域去了也行.
            {
                if (nowIdPlusK != -1)
                {
                    ++Kcounter;
                    nowIdPlusK = linkedList[nowIdPlusK].next;
                }
            }
            //從while到下面這一段所有的作用就是來找後面還有沒有K個數.當然更好的方法好像是周遊一遍用除法做
            if (Kcounter == K)
            {
                for (int i = 0; i < K; i++)
                {
                    s.push(linkedList[nowId]);
                    nowId = linkedList[nowId].next;
                }
                for (int i = 0; i < K; i++)
                {
                    resultList.push_back(s.top());
                    s.pop();
                }
            }
            else
            {
                while (nowId != -1)
                {
                    resultList.push_back(linkedList[nowId]);
                    nowId = linkedList[nowId].next;
                }
                break;
            }
        }
    }

    //output
    for (int i = 0; i < resultList.size() - 1; i++)
    {
        printf("%05d %d %05d\n", resultList[i].id, resultList[i].key, resultList[i + 1].id);
    }
    printf("%05d %d -1", (resultList.end() - 1)->id, (resultList.end() - 1)->key);
    return 0;
}

           

運作用時

結尾

看在我寫了這麼多注釋的份上可以給我點個贊嘛,求求惹=]砰砰砰,給我加點寫下去的油呀@[email protected]

也歡迎關注我的CSDN賬号呀,接下來兩個月我應該會按這個格式更新所有的PTA甲級題目

**開心code每一天**