操作 Linked List

題目敘述

相信大家都已經學會如何在 linked list 加入與刪除節點，請大家實作四個函式，分別是 append, insert, deleteNode 和 print。

• void append(Node *&head, int value)

  • 在 linked list 尾端新增值為 value 的節點。

• void insert(Node *&head, int index, int value)

  • 將值為 value 的節點插入 linked list 索引值為 index 的位置。

• void deleteNode(Node *&head, int value)

  • 在 linked list 刪除值為 value 的節點

• void print(Node *head)

  • 印出 linked list 所有值，每印出一個值請換行，包含最後一個值也要換行！

你上傳的函式將被放在下列程式中執行：

#include "lib0612.h"

int main() {
  Node *head = nullptr;

  int command;

  while (true) {
    cin >> command;

    switch (command) {
      case APPEND: {
        int value;
        cin >> value;
        append(head, value);
        break;
      }
      case INSERT: {
        int index, value;
        cin >> index >> value;
        insert(head, index, value);
        break;
      }
      case DELETE: {
        int value;
        cin >> value;
        deleteNode(head, value);
        break;
      }
      case PRINT: {
        print(head);
        break;
      }
      case BREAK: {
        // 釋放 Linked List 的記憶體
        Node *current = head;
        while (current != NULL) {
          Node *temp = current;
          current = current->next;
          delete temp;
        }

        // 結束程式
        return 0;
      }
    }
  }
}

注意第一行有 #include "lib0612.h"， lib0612.h 已經寫好了，你不需要寫，只需要參考它定義的 Node 和函式 prototype 即可。程式碼如下：

#ifndef _PREJUDGE_H_
#define _PREJUDGE_H_

#include <cstdlib>
#include <iostream>

#define APPEND 1
#define INSERT 2
#define DELETE 3
#define PRINT 4
#define BREAK 5

using namespace std;

// Linked List 節點
struct Node {
  // 節點的值
  int value;

  // 下一個節點的指標
  Node* next;

  // 建立節點時，將 value 初始化為 0，next 初始化為 NULL
  Node() {
    value = 0;
    next = NULL;
  }
};

void append(Node *&head, int value);
void insert(Node *&head, int index, int value);
void deleteNode(Node *&head, int value);
void print(Node *head);

#endif

你需要上傳的程式碼會像下面這樣，請務必記得在第一行寫下 #include "lib0612.h"。

#include "lib0612.h"

void append(Node *&head, int value) {
  // TODO
}

void insert(Node *&head, int index, int value) {
  // TODO
}

void deleteNode(Node *&head, int value) {
  // TODO
}

void print(Node *head) {
  // TODO
}

所有輸入的指令都是合法的，不需要做錯誤處理，且 linked list 中不會出現兩個節點有相同的值。

輸入格式

輸入包含 N 行，$0$ $<$ $N$ $<$ $1000$，每一行表示一個指令，由幾個整數組成，中間用空白分隔。
第一個整數表示這行要執行的指令：

• 第一個整數為 1 表示在 linked list 尾端插入節點，這時第二個整數表示要插入的節點的值
• 第一個整數為 2 表示在 linked list 索引值為 index 的地方插入節點，這時第二個整數表示 index，第三個整數表示要插入的節點的值
• 第一個整數為 3 表示刪除一個節點，第二個整數表示要刪除的節點的值
• 第一個整數為 4 表示印出整個 linked list
• 第一個整數為 5 表示結束程式。

你不需要擔心如何處理 input，我們已經妥善處理，你只需要實作四個函式即可。

輸出格式

在某一行的第一個整數為 4 的時候，表示要印出整個 linked list，請依序印出每個節點的值並換行，包含印出最後一個節點也要換行！

範例測資

範例輸入

1 1
1 2
1 3
4
2 0 4
3 1
4
5

範例輸出

1
2
3
4
2
3

範例說明

執行流程：

1. 輸入 1 1
   在 linked list 尾端插入值為 1 的節點，list 為 1。

2. 輸入 1 2
   在 linked list 尾端插入值為 2 的節點，list 為 1, 2。

3. 輸入 1 3
   在 linked list 尾端插入值為 3 的節點，list 為 1, 2, 3。

4. 輸入 4
   印出 linked list，也就是輸出

1
2
3

5. 輸入 2 0 4
   在 index 為 0 的地方插入值為 4 的節點，list 變成 4, 1, 2, 3。

6. 輸入 3 1
   將值為 1 的節點移除，list 變成 4, 2, 3。

7. 輸入 4
   印出 linked list，也就是輸出

4
2
3

8. 輸入 5
   結束程式。