链表的定义
面试时，需要自己手写...
// 单链表
struct ListNode {int val; // 节点上存储的元素ListNode *next; // 指向下一个节点的指针ListNode(int x) : val(x), next(NULL) {} // 节点的构造函数
};【构造函数可以省略，C++默认生成一个构造函数，但是这个构造函数不会初始化任何成员变量】
//自己定义构造函数初始化节点
ListNode* head = new ListNode(5);//使用默认构造函数初始化节点
ListNode* head = new ListNode();
head->val = 5;203.移除链表元素
2024.11.09
题目：给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。力扣题目链接
说明一下，使用C++来做leetcode，如果移除一个节点之后，没有手动在内存中删除这个节点，leetcode依然也是可以通过的，只不过，内存使用的空间大一些而已，但建议依然要养成手动清理内存的习惯。当然如果使用java ，python的话就不用手动管理内存了。
此处的链表是单链表，所以找不到前节点，只能找到后节点。
然后要删去头结点处理会比较特殊，所以头结点和其他节点要分开处理，除非你设一个虚拟头结点指向头结点，就可以统一处理方式，这也是一种方法。
我是对二者分开处理。如果前面n个val的值都是val，那么每次删除完之后，头节点又是待删除节点，所以不要使用if要使用while。
两次处理
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* removeElements(ListNode* head, int val) {//删除头结点的情况while(head != NULL && head -> val == val) //这里不可以用if，因为可能一连串的val都在链表前端，会导致删完头结点后，下一个头结点还是等于val{ListNode* temp = head;head = head -> next;delete temp;}//为什么cur指向head，因为除了头结点外，其他被删除节点都在head后面，单链表不能找前节点，只能用nextListNode* cur = head;//删除非头节点while(cur != NULL && cur -> next != NULL){if(cur -> next -> val == val){ListNode* temp = cur -> next;cur -> next = cur -> next -> next;delete temp;}else{cur = cur -> next;}}return head;}
};统一处理
class Solution {
public:ListNode* removeElements(ListNode* head, int val) {ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点dummyHead->next = head; // 将虚拟头结点指向head，这样方便后面做删除操作ListNode* cur = dummyHead;while (cur->next != NULL) {if(cur->next->val == val) {ListNode* tmp = cur->next;cur->next = cur->next->next;delete tmp;} else {cur = cur->next;}}head = dummyHead->next;delete dummyHead;return head;}
};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的节点。
有个值得注意的点，这里的index应该是从0开始的....
class MyLinkedList {
public:// 单链表结构体struct LinkedNode {int val;LinkedNode* next;LinkedNode(int val) : val(val), next(nullptr) {}};// 初始化链表MyLinkedList() {dummyNode = new LinkedNode(0); // 虚拟头结点length = 0;}int get(int index) {if(index > (length -1) || index < 0){return -1;}LinkedNode* temp = dummyNode -> next;while(index--){temp = temp -> next;}return temp -> val;}void addAtHead(int val) {LinkedNode* newNode = new LinkedNode(val); //新键结点//顺序不可调换，因为如果是dummyNode先指向newNode，那么dummyNode指向头结点的next就断了newNode -> next = dummyNode -> next;dummyNode -> next = newNode;length++;}void addAtTail(int val) {LinkedNode* newNode = new LinkedNode(val); //新键结点LinkedNode* temp = dummyNode;while(temp->next){temp = temp -> next;}temp->next = newNode;length++;}void addAtIndex(int index, int val) {if(index > length)return;if(index == length){addAtTail(val);return; }LinkedNode* newNode = new LinkedNode(val); //新键结点LinkedNode* temp = dummyNode;while(index--) {temp = temp -> next;}newNode -> next = temp -> next;temp -> next = newNode;length++;}void deleteAtIndex(int index) {if(index < 0 || index >= length) // 确保 index 在有效范围内return;LinkedNode* cur = dummyNode;while(index--) {cur = cur->next; // 遍历到目标节点的前一个节点}LinkedNode* temp = cur->next; // 获取目标节点cur->next = cur->next->next; // 删除目标节点delete temp; // 释放内存length--;}private:LinkedNode* dummyNode; // 虚拟头结点int length; // 链表长度
};前面一直忘记声明变量，一直报错，断断续续修改了2h，感觉自己基本告别计算机行业了....
未完待续....
