链表的基础操作2
前言
本节课我们将通过输出第m个元素的操作加深对链表的理解。

代码编写
依旧先把代码的基础结构给搭建好，上节课我们已经学习了链表结构体的书写，现在你是否能完整的写出定义链表节点的结构体呢？

#include <iostream>
using namespace std;
// 定义链表节点结构体
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};
int main() {
  
}
int n, k, m;
cin >> n >> k; // 输入n和k, n 表示需要构建的链表的长度，k 代表输入的 m 的个数。
ListNode* dummyHead = new ListNode(0); // 创建了一个虚拟头结点
和上一节内容相似，依旧需要使用for 循环，根据读取的 n 值，迭代读取 n 个整数，构建链表。

for (int i = 0; i < n; i++) { // 或者使用while(n--)
      int val; // 变量val接收输入的val值
    cin >> val;
    ListNode *newNode = new ListNode(val); // 构造一个新的节点
    cur -> next = newNode; // 将新节点接入链表
    cur = cur -> next;      // cur 指向下一个节点
}
上面的操作完成之后，链表就成功构建了，我们需要根据题目要求读取k个m，并输出这k个值

while(k--) {
  cin >> m;  // 输入k个m, m表示需要输出的节点的顺序
}
每次找到第m个节点都需要从头节点开始遍历，所以将 cur 重新指向虚拟头结点，以便重新遍历链表。

cur = dummyHead; // cur重新指向虚拟头节点，以便重新遍历链表
image-20230920173507813

使用 while 循环，寻找链表中的第 m 个元素, 只要cur没有指向null,就一直循环下去

while(m--) {
  if(cur != NULL) {
    cur = cur->next;  // 找到第m个节点
  } else {
    break;
  }
}
当while循环结束后，如果cur指向null,说明输入的m已经超出了链表的长度，如果cur还是指向dummyNode说明没有进入到while循环，也就是m=0，这两种情况都是m位置不合法的情况。

// cur == NULL 表示 m 超出了链表长度
// cur == dummyHead 表示 m = 0
if (cur == NULL || cur == dummyHead) {
  cout << "Output position out of bounds." << endl;
} else {
  // cur表示第m个节点，正常输出cur节点的val值
  cout << cur->val << endl;
}
完整代码如下：

#include <iostream>
using namespace std;
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};
int main() {
    int n, val, m, k;
    ListNode* dummyHead = new ListNode(0); // 创建了一个虚拟头结点
    cin >> n >> k;
    ListNode* cur = dummyHead; // 定义一个指向当前节点的指针 cur，初始指向虚拟头结点
    for (int i = 0; i < n; i++) { // 或者使用while(n--)
        cin >> val;
        ListNode* newNode = new ListNode(val); // 构造一个新的节点
        cur -> next = newNode; // 将新节点接入链表
        cur = cur -> next;      // cur 指向下一个节点
    }

    while (k--) {
        cin >> m;
        cur = dummyHead;
        while (m--) { // 寻找链表里第m个元素
            if(cur != NULL) cur = cur->next;
            else break;
        }
        // cur == NULL 表示 m 超出了链表长度
        // cur == dummyHead 表示 m = 0
        if (cur == NULL || cur == dummyHead) cout << "Output position out of bounds." << endl;
        else cout << cur->val << endl;
    }
}
 
结语
本节课我们通过输出链表第m个元素练习了链表节点的定义和链表的插入和遍历操作，这些基本操作在链表相关的题目中是不可缺少的，大家一定要多多练习。