当前位置：首页 > backend >正文

链表day3

backend 2025/5/22 13:43:48

链表定义

struct ListNode{int val;ListNode *next; //next是一个指针变量，存储的是地址，是ListNode类型的地址ListNode(int x) : val(x),next(nullptr){} //也就是说ListNode必须接受一个int x，next指针默认为nullptr，值由外部指定，指针默认置空。
}
//其中 ： 表示初始化列表，允许对象在构造时直接初始化成员变量，而非先初始化再赋值// 然后初始化一个链表
ListNode* head =  new ListNode(5)  //如果不构造构造函数，就无法一边初始化一边赋值
以下这种方式更好：
struct ListNode{int val;ListNode* next;ListNode(int x,ListNode* next=nullptr):val(x),next(next){} //首先，传入x和next变量（next变量默认为null），然后再将val初始化为x，next初始化为传入的next(如果没有传入，则默认为null)
};

->用法和*用法

ListNode* dummyhead = new ListNode(0);
dummyhead->next = head;//next也是一个指针变量，存放的是一个ListNode类型的地址。->用于访问指针访问成员，dummyhead->next 等价于 (*dummyhead).next

*表示解引用，*(指针变量）=指针变量存放的地址指向的变量。
*dummyhead实际上就是指向一个ListNode变量(val=0,next=...)

203 移除链表元素

思路很简单，记得free就行，其次记得使用一个dummy_head用于方便删除头结点

class Solution{
public:ListNode* removeElements(ListNode* head,int val){ListNode* dummyhead = new ListNode(0);dummyhead->next = head;ListNode* cur = dummyhead;while(cur->next != nullptr){ //也就是下一个变量不为空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设计链表

收获：
第一：构造函数中的成员变量仅作用于构造函数，若类中其他函数需要使用，需要在private中进行声明。还有个坑，第一，在private中进行声明以后，在private的构造函数中直接定义就行，不用声明，也就是直接val = 0,而不是int val =0


class MyLinkedList {//构造函数的作用是初始化这些成员变量，而非重新声明局部变量。
public:struct ListNode{int val;ListNode* next;ListNode(int x,ListNode* next = nullptr) : val(x),next(next){}};MyLinkedList() {//MyLinkedList() 初始化 MyLinkedList 对象dummyhead = new ListNode(0);//在private中已经声明，这里可以使用size = 0; //在private中已经声明，这里可以使用}int get(int index) {//int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 if(index>(size-1)||index<0){return -1;}ListNode* cur = dummyhead->next;while(index--){cur = cur->next;}return cur->val;}void addAtHead(int val) {//void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。ListNode* newNode = new ListNode(val);newNode->next = dummyhead->next;dummyhead->next = newNode;size++;}void addAtTail(int val) {//void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。ListNode* NewNode = new ListNode(val);ListNode* cur = dummyhead;while(cur->next){cur = cur->next;}cur->next = NewNode;size ++;}void addAtIndex(int index, int val) {//void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。if (index>size) return;if (index <0) index=0;ListNode* newNode = new ListNode(val);ListNode* cur = dummyhead;while(index--){cur  = cur->next;}newNode->next = cur->next;cur->next = newNode;size ++;}void deleteAtIndex(int index) {//void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。if(index>=size || index<0){return;}ListNode* cur = dummyhead;while(index--){cur = cur->next;}ListNode *tmp = cur->next;cur->next = cur->next->next;delete tmp;//删除了tmp以后，并非就指向null，而是随机值，如果不加上一句tmp = null,会变成野指针，//如果tmp后面又被使用了，会指向不知道那个内存空间tmp = nullptr;size --;}
private:int size;ListNode* dummyhead;};
/*** Your MyLinkedList object will be instantiated and called as such:* MyLinkedList* obj = new MyLinkedList();* int param_1 = obj->get(index);* obj->addAtHead(val);* obj->addAtTail(val);* obj->addAtIndex(index,val);* obj->deleteAtIndex(index);*/

206 反转链表

class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* temp;ListNode* cur = head;ListNode* pre = nullptr;while(cur){temp = cur->next;//保存cur的下一个节点cur->next = pre; //将cur指向前面pre = cur;//将pre指针右移cur = temp;//将cur指针右移}return pre;}
};