題目描述

請編寫一個程序，實現以下鏈表操作：構建一個單向鏈表，鏈表中包含一組整數數據。

1. 實現在鏈表的第 n 個位置插入一個元素，輸出整個鏈表的所有元素。
2. 實現刪除鏈表的第 m 個位置的元素，輸出整個鏈表的所有元素。

要求：

1. 使用自定義的鏈表數據結構。
2. 提供一個 linkedList 類來管理鏈表，包含構建鏈表、插入元素、刪除元素和輸出鏈表元素的方法。
3. 在 main 函數中，創建一個包含一組整數數據的鏈表，然後根據輸入的 n 和 m，調用鏈表的方法插入和刪除元素，並輸出整個鏈表的所有元素。

輸入描述

每次輸出只有一組測試數據。
每組的第一行包含一個整數 k，表示需要構建的鏈表的長度。
第二行包含 k 個整數，表示鏈表中的元素。
第三行包含一個整數 S，表示後續會有 S 行輸入，每行兩個整數，第一個整數為 n，第二個整數為 x ，代表在鏈表的第 n 個位置插入 x。
S 行輸入...
在 S 行輸入後，後續會輸入一個整數 L，表示後續會有 L 行輸入，每行一個整數 m，代表刪除鏈表中的第 m 個元素。
L 行輸入...

輸出描述

包含多組輸出。
每組第一行輸出構建的鏈表，鏈表元素中用空格隔開，最後一個元素後沒有空格。
然後是 S 行輸出，每次插入一個元素之後都將鏈表輸出一次，元素之間用空格隔開，最後一個元素後沒有空格；
如果插入位置不合法，則輸出“Insertion position is invalid.”。
然後是 L 行輸出，每次刪除一個元素之後都將鏈表輸出一次，元素之間用空格隔開，最後一個元素後沒有空格；如果刪除元素後鏈表的長度為0，則不打印鏈表。
如果刪除位置不合法，則輸出“Deletion position is invalid.”。
如果鏈表已經為空，執行刪除操作時不需要打印任何數據。

輸入示例

5
1 2 3 4 5
3
4 3
3 4
9 8
2
1
0

輸出示例

1 2 3 3 4 5
1 2 4 3 3 4 5
Insertion position is invalid.
2 4 3 3 4 5
Deletion position is invalid.

提示信息

鏈表為空的時候，不打印

點擊查看代碼 

#include<iostream>
using namespace std;

struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};

void printLinklist(ListNode* dummyHead){
ListNode* cur = dummyHead;
while(cur -> next != nullptr && cur -> next -> next != nullptr){ //遍歷到鏈表倒數第二個節點
  cout << cur -> next -> val << ' ';// 輸出當前cur的下一個節點值,並加空格,所以實際只有最後一個沒打印
  cur = cur -> next;
}
cout << cur -> next -> val<< endl;//輸出最後一個節點值

}

int main() {

int k,val;
cin >> k;
int listLen = k;//記錄鏈表長度，用來控制非法輸入輸出

ListNode* dummyHead = new ListNode(0);//設置虛擬頭指針
ListNode* cur = dummyHead;

for(int i = 0;i < k;i++){//初始化鏈表
  cin >> val;
  ListNode* newNode = new ListNode(val);
  cur -> next = newNode;
  cur = cur -> next;
}

int s,n,x;
cin >> s;
for(int i = 0;i < s;i++){
  cin >> n >> x;
  if(n <= 0 || n > listLen){//判斷插入位置是否合法
    cout << "Insertion position is invalid." << endl;
    continue;
  }

  cur = dummyHead;//找到插入的前一位置
  for(int i = 1;i < n;i++){
    cur = cur -> next;
  }

  ListNode* newNode = new ListNode(x);//將新節點插入
  ListNode* tmp = cur -> next;
  cur -> next = newNode;
  cur -> next -> next = tmp;

  listLen++; //鏈表長度加1

  printLinklist(dummyHead);
}

  int l,m;
  cin >> l;
  while(l--){
    cin >> m;

    if( m<=0 || m > listLen){ //判斷刪除位置是否合法
      cout << "Deletion position is invalid." << endl;
      continue;
    }

    cur = dummyHead; //找到刪除前一位置
    for (int i = 1;i < m;i++) cur = cur -> next;

    cur -> next = cur -> next -> next;//刪除

    listLen--; //鏈表長度減1
    if(listLen != 0) printLinklist(dummyHead);//判斷鏈表是否為空
  }
return 0;
}

小結

先構建鏈表結構體

struct ListNode {
  int val;
  ListNode *next;
  ListNode(int x) : val(x), next(nullptr) {}
};

建立鏈表長度變量，避免插入刪除位置不合法，以及記錄鏈表是否為空

int listLen = k;//記錄鏈表長度，用來控制非法輸入輸出

再對鏈表初始化

ListNode* dummyHead = new ListNode(0);//設置虛擬頭指針
  ListNode* cur = dummyHead;

  for(int i = 0;i < k;i++){//初始化鏈表
    cin >> val;
    ListNode* newNode = new ListNode(val);
    cur -> next = newNode;
    cur = cur -> next;
  }

進行插入操作

先判斷插入位置是否合法

if(n <= 0 || n > listLen){//判斷插入位置是否合法
      cout << "Insertion position is invalid." << endl;
      continue;
    }

再找插入位置

cur = dummyHead;//找到插入的前一位置
    for(int i = 1;i < n;i++){
      cur = cur -> next;
    }

進行插入

ListNode* newNode = new ListNode(x);//將新節點插入
    ListNode* tmp = cur -> next;
    cur -> next = newNode;
    cur -> next -> next = tmp;

最後將鏈表長度加一

listLen++; //鏈表長度加1

打印

printLinklist(dummyHead);

刪除操作

判斷刪除位置是否合法

if( m<=0 || m > listLen){ //判斷刪除位置是否合法
    cout << "Deletion position is invalid." << endl;
    continue;
  }

找到刪除位置

cur = dummyHead; //找到刪除前一位置
for (int i = 1;i < m;i++) cur = cur -> next;

刪除

cur -> next = cur -> next -> next;//刪除

鏈表長度減一

listLen--; //鏈表長度減1

先判斷是否為空，再打印

if(listLen != 0) printLinklist(dummyHead);//判斷鏈表是否為空

打印函數

void printLinklist(ListNode* dummyHead){
  ListNode* cur = dummyHead;
  while(cur -> next != nullptr && cur -> next -> next != nullptr){ //遍歷到鏈表倒數第二個節點
    cout << cur -> next -> val << ' ';// 輸出當前cur的下一個節點值,並加空格,所以實際只有最後一個沒打印
    cur = cur -> next;
  }
  cout << cur -> next -> val<< endl;//輸出最後一個節點值 
}