长沙网站建设公司哪家好,收费网站建设视频教程免费下载,搭建网站宣传,线上商城简介链表
通过指针串联在一起的线性结构#xff0c;每个节点由数据域和指针域两部分组成。链表节点在内存中的存储通常不是连续的#xff0c;各节点通过指针连接在一起#xff0c;其内存分布大致如下图所示。 定义
单链表
struct ListNode {// DATATYPE 可以是任意存放数据的…链表
通过指针串联在一起的线性结构每个节点由数据域和指针域两部分组成。链表节点在内存中的存储通常不是连续的各节点通过指针连接在一起其内存分布大致如下图所示。 定义
单链表
struct ListNode {// DATATYPE 可以是任意存放数据的类型如int, string等DATATYPE val; ListNode *next;ListNode(DATATYPE v) : val(v), next(nullptr) {}
};双链表
双链表节点定义比单链表节点多一个指向前驱节点的指针域。
struct ListNode {DATATYPE val;ListNode *prev;ListNode *next;ListNode(DATATYPE v) : val(v), prev(nullptr), next(nullptr) {}
};删除
在单链表中删除一个节点需要将该节点的前驱元素的 next 指针指向该节点的后继元素。如果删除节点为头节点则仅需找到正确的头节点即可。 插入
在单链表中插入与删除相反但仍需要找到插入的位置。将插入节点的 next 指针指向插入位置的后继节点将插入位置的前驱节点指向插入节点。如果是头节点则仅需要将插入节点指向原来头节点将头节点标记为当前插入节点。 总结
链表在插入和删除上的时间复杂度为 O(1)在查询上的时间复杂度为 O(n)。
适用于数据量不固定频繁增删少量查询的场景。
解题技巧
额外的数据结构哈希表快慢指针虚拟头节点
面试笔试
在面试和笔试中对算法的要求应有所区分。
在笔试中题量多时间少我们要尽量采取写出容易想到并且时间复杂度符合要求的算法通常可以以空间换时间。
而在面试中的题通常难度更小为了给面试官留下深刻的影响应尽量写出低时间复杂度低空间复杂度能体现代码水平的代码。
Reference
通常难度更小为了给面试官留下深刻的影响应尽量写出低时间复杂度低空间复杂度能体现代码水平的代码。
Reference
代码随想录 (programmercarl.com)
