有的小伙伴说没有学过数据结构,对链表不是特别了解,所以今天我们就来对链表进行一个系统的总结,另外大家如果想提高算法思想的话,我建议还是要系统的学一下数据结构的。
给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。
双指针目前LC上涉及83道题,属于面试的一个高频范围区。我们根据标签分类是可以获取到一部分信息笔试考察范围点的。目前LC上一共是1989道题。概率为83/1989= 4.17%.
链表是一种常用的数据结构,它由若干个结点组成。每个结点都有两部分组成:数据域和指针域。数据域存储结点的值,而指针域则指向下一个结点。由于链表的每个结点都有指针域,所以链表可以动态分配内存。
前言 本系列主要讲解链表的经典题 注:划重点!!必考~ 反转链表 力扣链接:206. 反转链表 - 力扣(LeetCode) (leetcode-cn.com) 题目描述: 给你单链表的头节点 head ,请你反转链表,并返回反转后的链表 示例: 📷 提示: 链表中节点的数目范围是 [0, 5000] -5000 <= Node.val <= 5000 解题思路: 这里我们采用三指针进行反转链表: 指针cur进行遍历链表 指针next记录cur的下一个指针,防止反转时下一个节点地址丢
存在一个按升序排列的链表,给你这个链表的头节点 head ,请你删除所有重复的元素,使每个元素 只出现一次 。
前言 本系列主要讲解链表的经典题 注:划重点!!必考~ 找到链表的中间结点 牛客链接:链表中倒数第k个结点_牛客题霸_牛客网 (nowcoder.com) 题目描述: 输入一个链表,输出该链表中倒数第k个结点 示例: 📷 解题思路: 一般思路: 遍历链表两次 高效思路: 使用两个指针 快指针先走k步 慢指针再与快指针一起走 当快指针走完时,慢指针走到倒数第k个结点 注意:k的大小可能超过链表长度这一特殊情况 注:这里我们来实现高效思路 参考代码: /** * st
大家好,很高兴又和大家见面啦!!! 在上一个篇章中,我们详细的介绍了队列的顺序存储结构——循环队列。同时花费了大量的篇幅来介绍循环队列的实现逻辑与实现方式,最后我们还使用C语言通过两种方式是实现了循环队列,相信大家看完上一篇内容的话应该对循环队列及其基本操作的实现已经没什么问题了。如果对这些内容还有疑问的朋友可以在文章下方评论留言,或者私信博主,博主看到后都会回复的哦!
解题思路: 该题从问题来看, 并不是完全是右旋问题, 而是找到右旋后的头节点进行断链重连
前言 本系列主要讲解链表的经典题 注:划重点!!必考~ 链表分割 力扣链接:160. 相交链表 - 力扣(LeetCode) (leetcode-cn.com) 题目描述: 给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null 。 示例: 📷 提示: listA 中节点数目为 m listB 中节点数目为 n 0 <= m, n <= 3 * 104 1 <= Node.val <= 105 0 <= ski
最近在回顾数据结构与算法,有部分的算法题用到了栈的思想,说起栈又不得不说链表了。数组和链表都是线性存储结构的基础,栈和队列都是线性存储结构的应用~
存在一个按升序排列的链表,给你这个链表的头节点 head ,请你删除链表中所有存在数字重复情况的节点,只保留原始链表中 没有重复出现 的数字。
请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null。
给定一个链表以及一个目标值,把小于该目标值的所有节点都移至链表的前端,大于或等于目标值的节点移至链表的尾端,同时要保持这两部分在原先链表中的相对位置。
单向链表的反转是一个非常常见的链表类面试题,我在刷leetcode的过程中,发现了有许多链表题目的解法,都是以反转链表为基础进行的。所以我觉得有必要记录一下。
前言 本系列主要讲解链表的经典题 注:划重点!!必考~ 删除链表中等于给定值 val 的所有节点 力扣链接:203. 移除链表元素 给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 示例: 📷 提示: 列表中的节点数目在范围 [0, 104] 内 1 <= Node.val <= 50 0 <= val <= 50 解题思路: 这里我们选择使用尾插法,遍历链表把不是val的节点给尾插到一个新的链表上
前言 本系列主要讲解链表的经典题 注:划重点!!必考~ 找到链表的中间结点 力扣链接:876. 链表的中间结点 - 力扣(LeetCode) (leetcode-cn.com) 题目描述: 给定一个头结点为 head 的非空单链表,返回链表的中间结点 如果有两个中间结点,则返回第二个中间结点 示例: 📷 提示: 给定链表的结点数介于 1 和 100 之间 解题思路: 一般的思路: 一个个遍历,得到链表长度,在遍历链表长度的二分之一,就能得到中间结点 高效思路: 使用两个指
输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第1个节点。例如,一个链表有6个节点,从头节点开始,它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。
“数据结构与算法”不管是在Java还是在任何语言中都是核心基础知识,就像是盖楼的地基一样,它被广泛的应用于架构的最底层,对于这部分知识的掌握程度能够决定读者以后的高度。
链表(Linked List)是一种基础的数据结构,它在内存中以节点的形式存储数据,并通过指针来表示节点之间的关系。在Python中,虽然列表(List)通常更受欢迎,但对链表的理解仍然对于编写高效的代码和深入了解数据结构非常重要。
单向链表(又名单链表、线性链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过从头部开始,依序往下读取。
要遍历链表就是不断找到当前节点的next节点,当next节点是null时,说明是最后一个节点,停止遍历。
给你单链表的头指针 head 和两个整数 left 和 right ,其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表 。
前言 本系列主要讲解链表的经典题 注:划重点!!必考~ 链表分割 牛客链接:链表的回文结构_牛客题霸_牛客网 (nowcoder.com) 题目描述: 对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。 给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结构。保证链表长度小于等于900。 解题思路: 这里我们先找到中间结点(使用快慢指针法) 快指针每次走两个结点的位置,慢指针每次走一个结点的位置 快指针走到结束位置时,慢指针
做有关链表的题目,有个常用技巧:添加一个虚拟头结点(哨兵),帮助简化边界情况的判断。
这是 LeetCode 上的「19. 删除链表的倒数第 N 个结点」,难度为 Medium。
前言 本系列主要讲解链表的经典题 注:划重点!!必考~ 链表分割 牛客链接:链表分割_牛客题霸_牛客网 (nowcoder.com) 题目描述: 现有一链表的头指针 ListNode* pHead,给一定值x,编写一段代码将所有小于x的结点排在其余结点之前,且不能改变原来的数据顺序,返回重新排列后的链表的头指针。 解题思路: 因为需要相对顺序不变,所以我们选择用尾插法 要将小的放在前面,打的放在后面,这里我们可以选择使用两个链表 一个链接小的结点,另一个链接大的结点,最后再将大的链表尾插
这是 LeetCode 上的「24. 两两交换链表中的节点」,难度为 Medium。
前言 本系列主要讲解链表的经典题 注:划重点!!必考~ 合并两个有序链表 力扣链接:21. 合并两个有序链表 - 力扣(LeetCode) (leetcode-cn.com) 题目描述: 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的 示例: 📷 提示: 两个链表的节点数目范围是 [0, 50] -100 <= Node.val <= 100 l1 和 l2 均按 非递减顺序 排列 解题思路: 如果是到原链表本身上进行合并,则需要考虑的
链表(Linked List)是一种基本的数据结构,用于组织和管理数据。它是由一系列节点(Node)组成的数据结构,每个节点包含一个数据元素和指向下一个节点的引用。链表是一种非线性数据结构,与数组不同,它可以根据需要动态分配内存。
什么是链表,链表是一种通过指针串联在一起的线性结构,每一个节点是又两部分组成,一个是数据域一个是指针域(存放指向下一个节点的指针),最后一个节点的指针域指向null(空指针的意思)。
在计算机领域离不开算法和数据结构,而在数据结构中我们往往需要一些灵巧的结构去处理一些繁杂的数据,链表 就是这样一种能穿针引线般的帮助我们去解决这种问题的数据结构。
比如我们在 16:10:40s 入队一个消息 A,41s入队的消息 B,42s 入队消息C
然后先让 fast 往前走 n 步,slow 指针不动,这时候两个指针的距离为 n。
LinkedBlockingQueue的命名很规范,基本上是“闻其名,知其意”——链表阻塞队列,由此名称可知,该队列底层的数据结构是链表,并且该队列是可阻塞的。我们从IDEA中将LinkedBlockingQueue的类之间的关系截图如下所示:
https://leetcode-cn.com/problems/swap-nodes-in-pairs/
给你两个非空的链表,表示两个非负的整数。它们每位数字都是按照逆序的方式存储的,并且每个节点只能存储一位数字。
并发安全的链表队列 ConcurrentLinkedQueue 并发安全的链表队列,主要适用于多线程环境中;底层数据结构为链表,由于队列本身频繁的出队和进队,那么这个线程安全是如何保障 I. 数据结构 从命名可以基本推测底层数据结构应该是链表,结合源码看下具体的链表节点 private static class Node<E> { volatile E item; volatile Node<E> next; Node(E item) { UNSAFE.putOb
题意很简单,给定两个非空的链表。用逆序的链表来表示一个整数,要求我们将这两个数相加,并且返回一个同样形式的链表。
队列的数据存储结构可以是顺序表,也可以是链表,本篇使用 Python 来分别实现顺序队列和链队列。
大家好,今天和大家分享一个自定义队列的实现,这也是很多面试中,容易问到,或者直接让大家写的一个题目。围绕这个题目,那么我们首先需要分析如何实现,那就要结合队列的特点。队列这种数据结构的特点我想大家肯定随口都能说得出来,那就是“先进先出” 。 那么我们如何设计一个先进先出的数据结构呢,首先能够确定的是,它属于一个线性结构,那么线性结构的实现,其实我们可用的选择就比较多,比如数组, 比如链表。 在这两个的基础上,再来想如何设计一个队列,队列的话,无外乎两种常用的操作,一个是入队,一个是出队。 既然是先进先出的,那么入队的时候,肯定要把元素放到集合的末尾,同理,出队的时候,要把集合的头部(也就是第一个元素) 返回。所以明确了这样的需求,实现起来就好办了,同时我们还可以维护一个队列的长度。
像这样的,用原有节点进行赋值,就容易成环。 因为当我把一个原有节点直接挂载到另外一个节点之下时,其实是将其后续节点一并带过去了。
这是 LeetCode 上的「2059. 转化数字的最小运算数」,难度为「中等」。
基于链表阻塞队列LinkedBlockingQueue 基于链表的无边界阻塞队列,常用与线程池创建中作为任务缓冲队列使用 I. 底层数据结构 先看一下内部定义,与 ArrayBlockingQueue做一下对比,顺带看下这两者的区别及不同的应用场景 /** 队列的容量, or Integer.MAX_VALUE if none */ private final int capacity; /** 队列中实际的个数 */ private final AtomicInteger count = new At
链表是一种线性数据结构,由节点组成,每个节点包含数据和指向下一个节点的引用。链表的最后一个节点通常指向空值(null),表示链表的结束。链表可以分为单向链表和双向链表,区别在于节点是否有指向前一个节点的引用。
1. LinkedBlockingQueue 上篇中,说到了ArrayBlockingQueue阻塞队列。在ArrayBlockingQueue中,底层使用了数组结构来实现。 那么,提到数组了就不得不提及链表。作为两对成双成对的老冤家,链表也可以实现阻塞队列。 下面,就让我们进入今天的正题LinkedBlockingQueue!!!! LinkedBlockingQueue是一个使用链表实现的阻塞队列,支持多线程并发操作,可保证数据的一致性。 与ArrayBlockingQueue相同的是,LinkedBl
领取专属 10元无门槛券
手把手带您无忧上云