首页
学习
活动
专区
圈层
工具
发布
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    【Leetcode】反转链表 合并链表 相交链表 链表的回文结构

    【Leetcode21】合并两个有序链表 1.链接 合并两个有序链表 2.题目再现 3.三指针尾插法 思路:创建一个新的链表,分别遍历两个链表,小的就尾插到新链表,然后指针向后走一步,直到有一方为空时就结束循环...;结束循环后,判断哪个链表不为空,把不为空的尾插到新链表中去。...【Leetcode160】相交链表 1.链接 相交链表 2.题目再现 3.解法 1.先分别遍历两个链表,记录下两个链表的长度; 2.如果两个链表尾节点的地址一样,则说明它们相交,否则不相交,(注意是地址不是值...); 3.求出两个链表长度的差gap; 4.先让长的链表走差距步gap,短的链表先不动; 5.然后两个链表同时走一步,比较每走一步时两个链表当前节点的地址,如果一样,则说明找到了它们相交的起始位置...1.找到链表的中间节点; 2.逆置链表中间节点以后的部分,rmid 为后半部分逆置后的第一个节点; 3.头指针 head 和 rmid 同时向后遍历,若 head 的值不等于 rmid 的值,则不是回文结构

    59010

    面试必备|单链表反转思路图形解析

    01 — 单链表 链表玩的是指针操作,非常容易出错,尽管看似很简单。...返回 newhead 03 — 反转算法图形显示 我们试着将一个单链表反转,定义Reverse(list) API,实现此功能,比如对如下链表进行反转操作: ?...算法图形化表达出来,步骤1和2的图形: ? 步骤3的图形显示过程,全部罗列: 执行:tmpnext = next.next 后, ? 执行:next.next = newhead 后, ?...再次走一遍上述的过程后,节点3又添加到2--->1这个链表上,newhead依然指向反转后的链表的头部,反转后的链表:3-->2--->1....思路总结 next变量始终指向原链表的即将要添加到反转链表的节点, newhead始终指向反转链表的头。 每遍历一次,newhead增加一个节点,即next节点,直到next变为null为止。

    2K50

    【链表】:链表的带环问题

    前言: 链表的带环问题在链表中是一类比较难的问题,它对我们的思维有一个比较高的要求,但是这一类问题分析起来也是很有趣的,下面我就给大家讲一下链表的带环问题,并且带上几个例题进行分析。...喜欢的铁子们可以点点关注,感谢大家的支持。 1.链表的分类: ●根据链表,单向,双向,带头,不带头,循环,不循环,可以把链表分成八种。...虽然说有八种链表,但是常用的只有:不带头单向不循环链表,带头双向循环链表。 ●但是今天我们要看的是不带头单向不循环,但是内部带环的问题。 2.判断链表是否带环?...2.当fast进环的时候,slow还在环外。 3.当slow金环的时候,fast在环中的某个位置。也就是说,fast和slow差了N个位置,当fast和slow都进环的时候,就变成了追击问题。...先来看看这个等式: slow刚刚进环时: slow走过的路程为:L fast走过的路程为:L+k*C+C-N 因为fast的速度是slow的三倍,所以有3*L=L+k*C+C-N。

    50700

    链表和双向链表的实现

    前言 ---- 链表中的数据通过指针连接,添加、插入或删除节点只需要修改指针指向 实现思路 实现一个链表需要具备以下方法 在链表尾部添加节点 获取链表所有节点的数据 链表指定位置插入元素 获取链表指定位置的节点数据...获取节点在链表中的位置 更新链表指定位置的数据 移除链表指定位置的节点 移除链表中的指定节点 判断链表是否为空 获取链表长度 链表内部需要定义head指针和链表长度 实现代码 定义head指针和length...this.length += 1 } 获取链表所有节点的数据 toString() { //声明空字符串存储链表节点数据 let listString = '' //获取第一个节点...(linkedList.size()) 双向链表 双向链表的指针是双向的,前指针指向上一个节点,后指针指向下一个节点 head指向第一个节点,tail指向最后一个节点 双向链表实现思路 需要具备以下方法...尾部插入元素 任意位置插入元素 获取所有节点数据 正向遍历链表获取节点数据 反向遍历链表获取节点数据 获取指定位置的节点数据 获取指定数据在链表中的位置 更新指定位置的节点数据 移除指定位置的节点 移除指定数据的节点

    1.3K40

    Leetcode链表回文 链表分割 链表相交 环形链表I 环形链表II 获取链表中倒数k的节点

    因为是单链表我们需要将中间点的后续节点翻转,从而由最后一个节点开始走知道slow的下一个节点指向slow,将slow下一个节点给到cur对象,让cur的下一个节点指向slow。...两个参数一个为链表,一个为x值,将链表中的每一个节点的值与x值比较,小的放在左边,大的放到右边,并且两者的相对位置不变 我们定义两个区间链表来获取小于x的节点和大于x的节点 当链表的节点走完后,将p1...当p2的最后一个节点是总链表的其他节点时,它的next始终指向其他的节点 这里还需要加一个条件,将p2的最后一个节点的next置空。...=p2; return p1; } 3.链表相交 给两个单链表的头节点,让这两个链表相交,并返回相交的起始节点 求得两者的长度,因为知道了两者可能会相交,所以需要A和B同时走,然后相交...如果是其中有一个链表长度过长,我们需要让其链表长的提前走len1-len2步 然后连个链表同时走直到相交返回第一个相交的值 代码 public ListNode getIntersectionNode

    70900

    《链表篇》---相交链表

    pA 从链表 headA 的头部开始遍历,pB 从链表 headB 的头部开始遍历。 如果 pA 到达了链表 headA 的末尾(pA == null),就让它跳到链表 headB 的头部继续遍历。...同理,如果 pB 到达了链表 headB 的末尾(pB == null),就让它跳到链表 headA 的头部继续遍历。...当 pA 到达链表headA的末尾时,pA 被重置为链表headB的头部,这是为了让 pA 开始遍历链表headB。...类似地,当 pB 到达链表headB的末尾时,pB 被重置为链表headA的头部。 通过这种方式,两个指针在遍历完自己的链表后,会从对方的链表头开始遍历。...由于两个指针都会遍历两个链表的总长度,无论两个链表的长度是否相同,最终两个指针会在相交节点处相遇,或者同时到达链表的末尾(即没有相交节点的情况)。

    46910

    C语言-链表(单向链表、双向链表)

    链表结构介绍 在前面章节已经学习了数组的使用,数组的空间是连续空间,数组的大小恒定的,在很多动态数据存储的应用场景下,使用不方便;而这篇文章介绍的链表结构,支持动态增加节点,释放节点,比较适合存储动态数据的应用场景...链表的节点是不连续的,需要通过每个节点的指针,来找到上一个节点或者下一个节点的地址。...链表的每个节点就是一个结构体变量,节点里有一个或者两个指针,可以保存上一个节点和下一个节点的地址,方便遍历链表,删除、插入节点时定位位置。 2....实现的功能如下: 初始化链表头 插入节点的函数(链表任意位置插入,链表尾插入) 删除节点的函数(链表任意位置删除、链表尾删除) 遍历链表,输出链表里的所有信息 #include #include...=NULL) { if(next_p->next==head) //表示第一次插入节点 { next_p->next=new_p;

    3.7K41

    【Leetcode】重排链表、旋转链表、反转链表||

    重排链表 题目描述 给定一个单链表 L 的头节点 head ,单链表 L 表示为: L0 → L1 → … → Ln-1 → Ln 请将其重新排列后变为: L0 → Ln → L1 → Ln-1...提示: 链表的长度范围为 [1, 5 * 104] 1 <= node.val <= 1000 方法一: 将链表的每一个节点存在数组里,然后用下标访问的方式,交叉连接。...,然后将中点后的链表翻转成一个新的链表,最后将这个新链表和原链表切割掉中间节点之后的链表合并成一个新的链表,合并方式是交叉合并。...题目描述 给你一个链表的头节点 head ,旋转链表,将链表每个节点向右移动 k 个位置。...请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表 。

    60810

    Leetcode:相交链表,环形链表,环形链表||

    相交链表 题目描述 给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。...思路: 先分别遍历两个链表,得出两个链表的节点个数和两个链表节点数的差,再创建两个指针指向两个链表,让节点数较多的链表的指针先遍历这个差值的节点数,然后两个指针再同时遍历,当两个指针指向的节点的地址相同时...如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。...head ,返回链表开始入环的第一个节点。...为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。

    65810

    【数据结构】线性表 ② ( 链式存储结构 - 链表 | 链表分类 - 单链表 双链表 非循环链表 循环链表 | 链表优缺点 )

    一、链式存储结构 - 链表 链式存储结构 就是 链表 LinkedList ; 链式存储结构 ( 链表 ) : 数据 存储在 节点 中 , 每个节点包含 数据值 和 指向下一个节点的指针 ; 通过节点之间的指针关系...; 循环链表 : 如果 最后一个节点的指针 指向 第一个节点 , 那么这个链表就是循环链表 ; 链表可以分为以下四类 : 单链表 单循环链表 双链表 双循环链表 三、链表优缺点 链表 LinkedList...优点: 插入 / 删除 性能高 : 链表 的 插入 / 删除操作 只需要调整指针的指向,时间复杂度为 O(1) ; 动态空间分配: 链表 可以 根据实际需要 动态分配存储空间,大小可灵活调整。...消耗空间多 : 链表需要 额外的指针 来维护节点之间的关系,增加了存储空间的消耗。 线性表 选择 : 选择使用 顺序表 还是 链表,取决于具体的 应用场景 和 操作需求。...如果需要频繁执行 随机访问 操作,并且对插入和删除操作的效率要求不高,使用顺序表 ; 如果需要频繁执行 插入和删除 操作,并且对访问操作的效率要求不高,使用链表 ;

    1K40

    每日精讲:链表的回⽂结构,相交链表,环形链表I,环形链表II

    一 链表的回⽂结构 1题目链接:链表的回文结构_牛客题霸_牛客网 2题目描述: 对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。...— 请注意相交节点的值不为 1,因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。...换句话说,它们在内存中指向两个不同的位置,而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点,B 中第四个节点) 在内存中指向相同的位置。...4思路:这里只有两链表的尾节点一样就是相交链表,我们只要找到两个链表的长度差,让长链表先走长度差个节点在两个链表同时走判断是否相等即可。 三 环形链表I 1题目链接:141....如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。

    30610

    经典的带环链表问题(链表补充)

    环形链表1 运用快慢指针的方法,fast ,slow从头节点出发,快指针走两步,慢指针走一步,若有环,快指针先进环,后续如果慢指针和快指针相遇,则链表带环。转换成了追击问题。...证明:假设链表就是有环,slow(1步)进环时,fast(两步)与slow的距离为N,追击过程中,每走一次,N都会-1,最后到0。本题的思想证明,距离为0就是追上了。...那么是否存在N是奇数且C是偶数的情况呢, 假设从出发位置到进环的位置相差L,slow进环时,fast已经走了x圈,且fast与slow相差N: 进环时:slow走的距离->L fast走的距离->L+x...环形链表2 本题相较于第一个环形链表题,多了返回节点位置的步骤,所以最初思路也是通过快慢指针,快慢指针相遇,则证明有环存在,然后将两指针相遇点记为meet,再继续走,此时头节点也开始移动,meet与head...head通过相交链表的思路求解。

    33710

    【数据结构】线性表的链式表示之单链表

    问题或建议,请公众号留言; 如果你觉得对你有帮助,欢迎点赞 内容目录 线性表的链式表示之单链表单链表的特点单链表的储存结构单链表的结点单链表的储存结构 线性表的链式表示之单链表 顺序表的链式表示其实就是我们所...“熟知”的链表,链表分为: 单向链表---今天讲这个 双向链表 循环链表 单链表的特点 单链表作为线性表的一种,首先肯定是具备线性表的两种特点的: 除了首尾两个元素之外,每个元素的前面和后面只有一个数据元素...单链表的储存结构 C语言的链表可能是很多人的噩梦,因为要频繁用到指针操作。...单链表的结点 ?...以下是创建链表的图示:

    78640
    领券