文章目录
前言链表什么是链表LeetCode 203. 移除链表元素LeetCode 707. 设计链表LeetCode 206. 反转链表
总结
前言
链表题公式解：链表转数组->操作数组->数组转链表 打卡第三天~ 今天是链表专题~
链表
什么是链表
今天将结束数组，开始链表的学习，那么对于链表，他的结构与特点相比较数组还是有很大的差距的；
什么是链表 链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针）。
链表的入口节点称为链表的头结点也就是head。
链表的内存管理 数组是在内存中是连续分布的，但是链表在内存中可不是连续分布的。 链表是通过指针域的指针链接在内存中各个节点。 所以链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。 如图所示
链表-链表与数据性能对比
数组在定义的时候，长度就是固定的，如果想改动数组的长度，就需要重新定义一个新的数组。
链表的长度可以是不固定的，并且可以动态增删， 适合数据量不固定，频繁增删，较少查询的场景。
接下来进入正题,刷题环节~
LeetCode 203. 移除链表元素
203. 移除链表元素 文章讲解 视频讲解 状态 : AC
看到这题,我首先想到了之前做的题目 LeetCode 27 移除元素 其区别只在于,一个是操作链表,一个是操作数组 那么是不是可以先将链表元素存入数组中,再操作数组,最后转换为链表呢 这就是链表题的一种通解
AC代码示例:
class Solution {
public:
ListNode* removeElements(ListNode* head, int s) {
ListNode *p=head;
vector
// 一 将链表元素存入数组
while(p){
nums.push_back(p->val);
p=p->next;
}
// 二 对数组进行相应操作
int slow=-1,fast=0;
while(fast if(slow slow++; nums[slow]=nums[fast]; } fast++; } // 三 再转换为链表 if(slow+1>0) head->val=nums[0]; else return nullptr; head->next=nullptr; p=head; for(int i=1;i ListNode *Next=new ListNode(nums[i]); p->next=Next; p=p->next; } return head; } }; 时间复杂度:O(n)空间复杂度：O(n) (开辟数组空间) LeetCode 707. 设计链表 LeetCode 707. 设计链表 文章讲解 视频讲解 状态 : Debug 半小时 终于A了 这一题就得老老实实的掌握链表了 题目还是不错的,一题涉及了链表的增删改(?)查 看见就上手一顿操作,然后报错www,主要是index下标的问题 最后慢慢debug才整出来,但原来的太丑了 再看卡哥的讲解…自己重新写了一份 AC代码示例: class MyLinkedList { struct myList{ int val; myList* next; myList():val(0),next(nullptr){} myList(int a):val(a),next(nullptr){} myList(int a, myList* next_a):val(a),next(next_a){} }; public: MyLinkedList(){ listhead=new myList(0); list_size=0; } int get(int index) { if(index>=list_size) return -1; int count=0; myList* pmove=listhead; while(count != index){ count++; pmove=pmove->next; } return pmove->val; } void addAtHead(int val) { if(list_size==0){ myList* newnode=new myList(val); listhead=newnode; list_size++; return; } myList* newnode=new myList(val); newnode->next=listhead; listhead=newnode; list_size++; } void addAtTail(int val) { if(list_size==0){ myList* newnode=new myList(val); listhead=newnode; list_size++; return; } myList* pmove=listhead; while(pmove->next){ pmove=pmove->next; } myList* newnode=new myList(val); pmove->next=newnode; list_size++; } void addAtIndex(int index, int val) { if(index>list_size) return; if(index==0){ addAtHead(val); return; } int count=0; myList* pmove=listhead; while(count+1 != index){ count++; pmove=pmove->next; } list_size++; myList* newnode=new myList(val,pmove->next); pmove->next=newnode; } void deleteAtIndex(int index) { if(index>=list_size) return; int count=0; myList* pmove=listhead; if(index==0){ listhead=listhead->next; list_size--; return; } while(count+1 != index){ count++; pmove=pmove->next; } pmove->next=pmove->next->next; list_size--; } int list_size; myList* listhead; }; 时间复杂度: 涉及 index 的相关操作为 O(index), 其余为 O(1)空间复杂度: O(n) LeetCode 206. 反转链表 LeetCode 206. 反转链表 文章讲解 视频讲解 状态 : 2分钟搞定 这题就能用公式搞定 链表转数组->操作数组->数组转链表 但建议还是手写一遍常规解,毕竟学习的是链表嘛! AC代码示例(公式解): class Solution { public: ListNode* reverseList(ListNode* head) { ListNode *pmove=head; vector //一. 链表转数组 while(pmove){ nums.push_back(pmove->val); pmove=pmove->next; } //二. 操作数组 reverse(nums.begin(),nums.end()); //三. 数组转链表 if(nums.size()>0) head->val=nums[0]; else return nullptr; head->next=nullptr; pmove=head; for(int i=1;i ListNode *Next=new ListNode(nums[i]); pmove->next=Next; pmove=pmove->next; } return head; } }; 时间复杂度: O(n)空间复杂度: O(n) (开辟数组) 当然常规解也是要学习的~ AC代码示例(公式解): class Solution { public: ListNode* reverseList(ListNode* head) { ListNode* temp; ListNode* cur = head; ListNode* pre = NULL; while(cur) { temp = cur->next; cur->next = pre; pre = cur; cur = temp; } return pre; } }; 时间复杂度: O(n)空间复杂度: O(1) 总结 坚持 2024- 4-19 文章来源
发表评论