题目 输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。...示例 1： 输入：head = [1,3,2] 输出：[2,3,1] 限制： 0 <= 链表长度 <= 10000 第一次 //使用栈的特性先进后出 //复杂度O（n） public int[] reversePrint...] = result[i].val; count--; } return resultV2; } 第三种解决方案 //纯O（n）的复杂度
2.4 方法对比 LinkedList 实现了 Queue 接口，在新增、删除、查询等方面增加了很多新的方法，这些方法在平时特别容易混淆，在链表为空的情况下，返回值也不太一样，我们列一个表格，方便大家记录...： 方法含义 返回异常 返回特殊值 底层实现 新增 add(e) offer(e) 底层实现相同 删除 remove() poll(e) 链表为空时，remove 会抛出异常，poll 返回 null。...查找 element() peek() 链表为空时，element 会抛出异常，peek 返回 null。... // 索引位置变化 nextIndex--; return lastReturned.item; } 这里复杂点体现在需要判断 next 不为空和为空的场景...== lastReturned 的场景分析：从尾到头递归顺序，并且是第一次迭代，并且要删除最后一个元素的情况下 // 这种情况下，previous() 方法里面设置了 lastReturned
从根开始⽐较，查找x，x⽐根的值⼤则往右边⾛查找，x⽐根值⼩则往左边⾛查找。...最多查找⾼度次，⾛到到空，还没找到，这个值不存在。 如果不⽀持插⼊相等的值，找到x即可返回 如果⽀持插⼊相等的值，意味着有多个x存在，⼀般要求查找中序的第⼀个x。...如下图，查找3，要 找到1的右孩⼦的那个3返回 当我们要查询4从根节点开始，比8小往左边走，比3大往右边走，比6小往左走,找到4了，返回true。....从根节点开始查询 ，cur不等于空，找到空了，就说明没有这个值。 小于当前节点往左边走，大于当前节点往右边走，等于就返回true。...如果要删除根节点，需要右节点的最左的那个节点的数值拿来替换。 我们发现10的左节点已经完成空了，那就是用10这个节点来替换了。 下面这个返回true，是查询到要删除的节点，就返回true.
，为空时返回undefined */ deleteHead(): T | undefined { /* 实现略 */ } /** * 移除并返回尾部节点的值 * @returns 尾节点的值...，为空时返回undefined */ deleteTail(): T | undefined { /* 实现略 */ } /** * 查看头部节点的值（不移除） * @returns 头节点的值...，为空时返回undefined */ getHead(): T | undefined { /* 实现略 */ } /** * 查看尾部节点的值（不移除） * @returns 尾节点的值...(); } /** * 从尾部出队 * @returns 队尾元素，为空时返回undefined */ dequeueRear(): T | undefined { return...适用场景包括：任务调度（高优先级任务先执行）、Dijkstra 最短路径算法（优先选择距离最近的节点）。
如果不为空，我们打印当前节点的数据，然后递归地访问左子节点和右子节点。这种顺序确保了根节点总是最早被访问，对于许多应用场景非常有效。...步骤如下： 1.初始化一个队列，将根节点入队。 2.当队列不为空，重复以下操作： 从队列中出队一个节点并访问（打印或记录）。 将该节点的左子节点和右子节点（如果存在）入队。...2.如果当前节点不为空，返回1（当前节点）加上左子树和右子树的节点个数。...非叶子节点：至少有一个子节点的节点。 步骤如下： 1.如果当前节点为空，返回0（没有叶子节点）。 2.如果当前节点是叶子节点（左右子节点均为空），返回1。...遍历过程： 将根节点入队，开始遍历。 从队列中出队节点，检查其是否为空。 对于每个非空节点，将其左右孩子入队。 一旦遇到空节点，标记后续节点必须都是空节点。
当从栈中删除元素时，将栈顶指针向下移动一位，并返回原来栈顶位置的元素。 使用数组实现栈的优点是简单直观，容易理解。但是，它也有一些局限性。...当从栈中删除元素时，将栈顶指针指向当前栈顶节点的下一个节点，并释放原来栈顶节点的内存。 使用链表实现栈的优点是可以动态地调整栈的大小，不会出现内存溢出的问题。...出栈（pop） 出栈操作是从栈顶删除一个元素。在进行出栈操作时，需要先检查栈是否为空。如果栈为空，则不能进行出栈操作。如果栈不为空，则将栈顶指针向下移动一位，并返回原来栈顶位置的元素。 3. ...判断栈是否为空（isEmpty） 判断栈是否为空操作是检查栈中是否有元素。如果栈顶指针指向栈底位置，则说明栈为空；否则，栈不为空。 四、栈的应用场景 1. ...当函数执行完毕时，这些信息被从栈中弹出。 3. 深度优先搜索 深度优先搜索是一种图的遍历算法。在深度优先搜索中，栈可以用来存储已经访问过的节点，以便在需要时进行回溯。 4.
如果栈已满，则抛出异常（对于固定大小的栈）或动态扩展栈的大小（对于动态大小的栈）。 pop(): 移除并返回栈顶元素。如果栈为空，则抛出异常。 peek(): 返回栈顶元素但不移除。...应用场景: 函数调用栈: 存储函数调用信息，包括局部变量、参数、返回地址等。这使得函数的嵌套和递归调用成为可能。...2.1 特点 FIFO: 队列的核心特性，决定了它的应用场景。 双端操作: 元素从队尾（rear）添加，从队首（front）删除。...enqueue操作将元素添加到rear位置，dequeue操作返回front位置的元素。 链表: 使用链表实现队列，队首作为链表的头节点，队尾作为链表的尾节点。...enqueue操作将新元素添加到链表尾部，dequeue操作删除链表头部节点。 应用场景: 进程调度: 操作系统使用队列管理等待执行的进程，确保先到达的进程先被执行。
如果尾节点为空，则队列为空，将首尾节点都指向当前节点。 如果尾节点不为空，证明队列中有其他节点，则将当前尾节点的nextWaiter指向当前节点，将当前节点置为尾节点。...while方法会从首节点顺着等待队列往后寻找waitStatus!=-2的节点，将当前节点的nextWaiter置为空。...如果当前节点的前驱节点为空，代表当前节点为首节点，则将next设置为首节点； 如果不为空，则将前驱节点的nextWaiter指向后继节点。 如果后继节点为空，则直接将前驱节点设置为尾节点。...，返回false；如果当前节点有前驱节点，则证明它在AQS队列中，但是前驱节点为空，说明它是头节点，而头节点是不参与锁竞争的，也返回false。...; } 将等待队列的头结点从等待队列转移到AQS队列中，如果转移失败，说明该节点已被取消，直接返回false，然后将first指向新的头结点重新进行转移。
以下逐一举例：单向链表每个节点只包含一个指向下一个节点的指针，最后一个节点的指针为空（null）。...首先需要做的是把element作为值传入，创建Node项。先来实现第一个场景：向为空的列表添加一个元素。...如果是，就返回它的位置 } index++; // 就继续计数 current = current.next; //检查列表中下一个节点 } return -1; }; 如果列表为空，或是到达列表的尾部...如果没有找到值，就返回-1。检查链表是否为空如果列表中没有元素，isEmpty方法就返回true，否则返回false。...remove(element)：从列表中移除一项。indexOf(element)：返回元素在列表中的索引。如果列表中没有该元素则返回-1。
堆（Heap）结构示意图 高频场景 1：Top K 问题 问题模式： 从海量数据中找出最大/最小的 K 个元素。 堆解法： 找最大 K 个： 维护一个最小堆，堆顶是当前 K 个元素中最小的。...Dijkstra 算法： 使用优先队列（最小堆） 存储 (distance, node)，每次从堆中取出当前距离最小的节点进行松弛操作。这是堆在图论中的核心应用。...求每层的最大值/平均值。 找到从根节点到叶节点的最短路径（BFS 首次到达叶节点）。 序列化/反序列化二叉树（按层存储）。...高效解法 (后序遍历)： 如果 root 为空，或 root 等于 p 或 q，直接返回 root。...如果 left 非空，right 为空：说明 LCA 在左子树中，返回 left。 如果 right 非空，left 为空：说明 LCA 在右子树中，返回 right。 如果都为空：返回 None。
背景说明 一个系统可为其他系统提供能力或者直接为UI层提供数据，在设计系统测试方案时应考虑上游调用的各种场景，不仅考虑顺利且正向思维操作的场景，还应逆向的场景。...具体来说，例如一个简单的积分充值接口，积分币数量不可空。从系统本身来说，无充值数量此充值单据即无意义。而充值数量会作为积分消费、失效等接口调用的起始数据源依赖。...依次对 必传参数设置为空进行请求，此时接口不可调用成功，无数据生成，同时关注接口返回信息明确性，如果接口返回提示文案为“XX不可为空”一目了然，极大方便定位问题，提高效率。...03 流程节点限制 流程节点限制，即需严格遵守流程流转。当调用某就流程时，必须由上一节点调用。 为何需做流程节点限制？ 支付单系统的流程为流程1：创建、支付完成、支付后的使用，流程2：创建、取消。...测试不合理流程节点下的调用，包含单一流程和交叉流程，观察接口返回及数据状态。例如单据状态为创建时调用使用接口，单据状态为完成时调用取消接口。
常见的链表类型有单向链表（单链表），双向链表和循环链表。 以下逐一举例： 单向链表 每个节点只包含一个指向下一个节点的指针，最后一个节点的指针为空（null）。...首先需要做的是把element作为值传入，创建Node项。 先来实现第一个场景：向为空的列表添加一个元素。...如果是，就返回它的位置 } index++; // 就继续计数 current = current.next; //检查列表中下一个节点 } return -1; }; 如果列表为空...如果没有找到值，就返回-1。 检查链表是否为空 如果列表中没有元素，isEmpty方法就返回true，否则返回false。...如果列表中没有该元素则返回-1。 removeAt(position)：从列表的特定位置移除一项。 isEmpty()：如果链表中不包含任何元素，返回true，如果链表长度大于0则返回false。
二叉搜索树的概念 ⼆叉搜索树⼜称⼆叉排序树，它或者是⼀棵空树，或者是具有以下性质的⼆叉树: 若它的左子树不为空，则左子树上所有结点的值都小于等于根结点的值 若它的右子树不为空，则右子树上所有结点的值都⼤...true } Node* parent = nullptr; // 用于跟踪当前节点的父节点 Node* cur = _root; // 从根节点开始查找合适的位置...= cur; // 将新节点作为父节点的左子节点 } return true; // 插入成功，返回 true } 4....二叉搜索树的查找 从根开始比较，查找x，x比根的值大则往右边⾛查找，x比根值小则往左边⾛查找。 最多查找⾼度次，⾛到到空，还没找到，这个值不存在。...如果不支持插入相等的值，找到x即可返回 如果支持插入相等的值，意味着有多个x存在，⼀般要求查找中序的第⼀个x。
链表按此结构对各节点的访问需从链表的头找起，后续节点的地址由当前节点给出。无论在表中访问哪个节点，都需要从链表的头开始，顺序向后查找。链表的尾节点由于无后续节点，其指针域为空，写作为NULL。...3.2 实现 [golang 双向链表] 节点定义 双向链表有两个指针，分别指向前一个节点和后一个节点 链表表头 prev 的指针为空，链表表尾 next 的指针为空 // 链表的一个节点 type ListNode...、表尾进行访问，定义了一个属性 len ，直接可以返回链表的长度，直接查询链表的长度就不用遍历时间复杂度从 O(n) 到 O(1)。...链表的长度 } // 创建一个空链表 func NewList() (list *List) { list = &List{ } return } // 返回链表头节点 func...// 从链表左边取出一个节点 func (l *List) LPop() (node *ListNode) { // 数据为空 if l.len == 0 { return
ue搜索场景: 1.二叉搜索树的概念 二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树: 若它的左子树不为空，则左子树上所有结点的值都小于等于根结点的值 若它的右子树不为空...1.从根开始比较，查找x，x比根的值大则往右边走查找，x比根值小则往左边走查找。...2.最多查找高度次，走到到空，还没找到，这个值不存在。 3.如果不支持插入相等的值，找到x即可返回 4.如果支持插入相等的值，意味着有多个x存在，一般要求查找中序的第一个x。...，并且这个3存在2两个，那么我们查找中序的第一个三就行了 5.二叉搜索树的删除 首先查找元素是否在二叉搜索树中，如果不存在，则返回false。...->_right = cur->_right; } } 现在我们要删除3这个节点的话 我们需要找到右子树中的最小节点 那么我们就在右子树中的左边进行最小节点的寻找操作 我们这里从6
与siftUp()方法类似，siftDown()方法不断地比较当前节点和它的子节点，并交换它们的位置，直到当前节点小于等于最小的子节点或子节点都为空。...合并多个有序数组：可以将多个有序数组的第一个元素放入PriorityQueue中，并且每次从PriorityQueue中取出最小的元素，直到PriorityQueue为空。...E peek()：返回PriorityQueue中的第一个元素，如果PriorityQueue为空，则返回null。...E poll()：移除并返回PriorityQueue中的第一个元素，如果PriorityQueue为空，则返回null。...boolean remove(Object o)：从PriorityQueue中移除指定元素。 int size()：返回PriorityQueue中的元素个数。
构造一个空的线性表。● Length(L):求表长。返回线性表L 的长度，即L 中数据元素的个数。● LocateElem(L,e): 按值查找操作。在表工中查找具有给定关键字值的元素。...删除表L 中第i 个位置的元素，并用e 返回删除元素的值。● PrintList(L): 输出操作。按前后顺序输出线性表L 的所有元素值。● Empty(L): 判空操作。...若L 为空表，则返回true, 否则返回false。● DestroyList(&L): 销毁操作。销毁线性表，并释放线性表L 所占用的内存空间。...二.线性表的顺序表示2.1定义线性表的顺序存储称为顺序表，逻辑顺序与物理存储顺序相同，是一种随机存取的存储结构位序：就是第几个，相当于下标但不是下标，数组的下标从0开始，位序从1开始2.2静态分配与动态分配一维数组可以静态分配也可以动态分配...为指向结构体的指针类型3.1.3 核心操作实现（1）初始化空链表// 初始化空链表（带头节点）bool InitList(LinkList *L) { *L = (LNode *)malloc(sizeof
让我们从底层实现开始深入了解这个强大的数据结构。 linkedList.jpg 底层数据结构 LinkedList的底层数据结构是双向链表。...往前遍历，找到对应索引的节点并返回。...如果要删除的元素是 null，则通过遍历链表找到第一个值为 null 的节点，然后调用 unlink(x) 方法删除该节点。删除成功后返回 true。...如果要删除的元素是 null，则通过遍历链表找到第一个值为 null 的节点，然后调用 unlink(x) 方法删除该节点。删除成功后返回 true。...使用场景 LinkedList适用于以下场景： 频繁的插入和删除操作： 由于链表的节点可以方便地插入和删除，适用于这类操作频繁的场景。
在经典的生产者/消费者模型中，生产者们将生产的元素放入队列，而消费者们从队列获取元素消费 当队列已满，我们会手动阻塞生产者，直到消费者消费再来手动唤醒生产者 当队列为空，我们会手动阻塞消费者，直到生产者生产再来手动唤醒消费者...抛出异常NoSuchElementException 返回值: 队满offer返回false，队空poll返回null 阻塞等待: 队满时put会阻塞线程 或 队空时take会阻塞线程 超时阻塞等待:...**********保证入队、出队操作的原子性，使用两个等待队列存储等待的生产者、消费者，适用于在并发量不大的场景** LinkedBlockingQueue LinkedBlockingQueue从名称上来看...(); //入队的等待队列 private final Condition notFull = putLock.newCondition(); } 从字段中，我们可以知道它使用单向链表的节点...后续首节点会一直指向值为空的虚拟节点 而真实的队头节点实际上是这个虚拟节点的next节点 来看看入队操作 public boolean offer(E e, long timeout, TimeUnit
队头（Front）：队列中第一个被添加的元素位于队头，但它不是永远位于队列的第一个位置，而是指按照入队顺序，最先应该被出队的元素的位置。在出队操作中，总是从队头移除元素。...接下来，对空队列和非空队列分别处理: 空队列直接让首尾指针都指向新节点 非空队列:尾指针指向节点的next指针指向新节点，尾指针再指向新节点 完成插入之后，size++ // 队尾入队列 void...返回size // 获取队列中有效元素个数 int QueueSize(Queue* q) { assert(q); return q->size; } 队列判空 形参判空 返回size==0的结果...// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 int QueueEmpty(Queue* q) { assert(q); return q->size == 0; } 五、C语言实现代码...Q);//队列销毁 } int main() { test1(); return 0; } 测试结果 六、应用场景 单链表队列的应用场景非常广泛，几乎在所有需要按照特定顺序处理数据的情况下都可以看到它的身影
云服务器
ICP备案
实时音视频
即时通信 IM
对象存储
