本文主要是介绍代码随想录算法训练营第33期day03: 第一章链表 part01，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
203. 移除链表元素 10分18
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
示例 1：
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
示例 2：
输入：head = [], val = 1
输出：[]
示例 3：
输入：head = [7,7,7,7], val = 7
输出：[]
数据结构中的头结点和 leetCode 的头结点
leetCode 中的默认的头结点是存储数据的，能可以为空，也参与题中所说的增删改查。但是，这与数据结构（严奶奶的）这本书所描述的数据结构并不相同，数据结构书上认为的链表的头结点一般是不存储数据的，若是要存储数据也一般是存储链表的长度，且头结点不参与链表的增删改查，头结点的作用在于统一链表的操作（空表和非空表），下面是 chatgpt 上的数据结构的说法。
所以知道了上面的区别，这道题也就好做了，只要把头节点当作链表的第一个有数据的结点（首元结点）来看就行，就当作题目并没有给出头节点，因此我们需要设置一个虚拟的头结点，方便对链表的操作。
代码实现
ListNode* removeElements(ListNode* head, int val) {ListNode* vitualHead = new ListNode(0); // 设置虚拟头结点vitualHead->next = head;ListNode* p = vitualHead;while (p->next != NULL) {if (p->next->val == val) p->next = p->next->next;else p = p->next;}head = vitualHead->next;delete vitualHead;return head;
}收获：发现了 leetCode 的头结点与我之前理解的头结点并不相同，以上也是链表的常规操作。
707. 设计链表
你可以选择使用单链表或者双链表，设计并实现自己的链表。单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。
如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。
实现 MyLinkedList 类：
- MyLinkedList() 初始化 MyLinkedList 对象。
- int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
- void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
- void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
- void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
- void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。
示例：
输入
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
输出: [null, null, null, null, 2, null, 3]
解释
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2); // 链表变为 1->2->3
myLinkedList.get(1); // 返回 2
myLinkedList.deleteAtIndex(1); // 现在，链表变为 1->3
myLinkedList.get(1); // 返回 3
注意事项+心得体会
这道题怎么说呢，一开始不知道 leetCode 默认头结点也存储数据，写出来的代码怎么都 ac 不了，补来补去，后来看了卡哥的题解，才感觉有点奇怪，才发现原来是规定不一样，还有就是那个 index 真的不要理解成第几个，就是索引。还有一个就是链表的长度，我一开始是自己加了个函数获取链表长度，后来看了卡哥题解，觉得声明一个全局变量确实好用。这道题挺锻炼链表的掌握，就是链表的增删改查。下次还得刷！
class MyLinkedList {
public:ListNode* head; // 创建空链表int _size; // 链表长度MyLinkedList() { // 初始化链表head = new ListNode(0);_size = 0;}/*获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。*/int get(int index) {if (index < 0 || index + 1 > _size) return -1;ListNode* p = head->next; // 索引 链表长度 = 索引+1while (index--) p = p->next;return p->val;}/*将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。*/void addAtHead(int val) { // 头插法ListNode* node = new ListNode(val);node->next = head->next;head->next = node;_size++; // 链表长度加一}/*将一个值为 val 的节点追加到链表中作为链表的最后一个元素。*/void addAtTail(int val) { // 尾插法ListNode* p = head;while (p->next) p = p->next; // 定位到链表尾端ListNode* node = new ListNode(val);node->next = p->next;p->next = node;_size++;}/*将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。*/void addAtIndex(int index, int val) {if (index > _size) return; // 如果 index 比长度更大，该节点将 不会插入 到链表中。if (index < 0) index = 0; // index < 0 默认插入到第一个ListNode* p = head;while (index--) p = p->next;ListNode* node = new ListNode(val);node->next = p->next;p->next = node;_size++;}/*如果下标有效，则删除链表中下标为 index 的节点。*/void deleteAtIndex(int index) {if (index < 0 || index >= _size) return; // index 等于下标那就是越界ListNode* p = head;while (index--) p = p->next;ListNode* q = p->next;p->next = q->next;delete q;_size--;}
};
206. 反转链表 11分07
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2]
输出：[2,1]
示例 3：
输入：head = []
输出：[]
解题思路+画图
这道题有两个思路
①简单思路（暴力）
重新创建一个新的头节点 head_，遍历 head 将 head 链表的结点利用头插法的方法插入 head_，最后返回 head_
②遍历中交换结点
ListNode* reverseList(ListNode* head) {if (head == NULL) return head;ListNode* p = head; // 头结点也存储数据ListNode* cur = NULL;while (p) { // 不断移动结点-->画图ListNode* q = p->next;p->next = cur;cur = p;p = q;}return cur; // 根据画图得
}收获：先画图，没有啥是一张图解决不了滴。
这篇关于代码随想录算法训练营第33期day03: 第一章链表 part01的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
