无锡网站建设上海韵茵,wordpress主题 单步调试,喀什网站建设百度推广,asp.net 跳转别的网站环形链表OJ题
1. 环形链表
链接#xff1a;141. 环形链表
描述#xff1a; 给你一个链表的头节点 head #xff0c;判断链表中是否有环。
如果链表中有某个节点#xff0c;可以通过连续跟踪 next 指针再次到达#xff0c;则链表中存在环。 为了表示给定链表中的环141. 环形链表
描述 给你一个链表的头节点 head 判断链表中是否有环。
如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。**注意pos 不作为参数进行传递 。仅仅 是为了标识链表的实际情况。
如果链表中存在环 则返回 true 。 否则返回 false 。 示例1 输入head [3,2,0,-4], pos 1 输出true 解释链表中有一个环其尾部连接到第二个节点。 示例2: 输入head [1,2], pos 0 输出true 解释链表中有一个环其尾部连接到第一个节点。 示例3 输入head [1], pos -1 输出false 解释链表中没有环。 提示 链表中节点的数目范围是 [0, 10^4] -10^5 Node.val 105 pos 为 -1 或者链表中的一个 有效索引 。
1.1思路 快慢指针
做这道题目之前我们需要明确一点 不能遍历链表因为链表带环。
链表带环是指链表的某个节点中存储的地址为这个节点前的某个节点的地址。而导致闭环 使遍历链表时无法停止走不到空无法停止。
所以我们这道题目采用的方法是快慢指针好巧又是快慢指针bushi
总体思路是 快指针走两步慢指针走一步。给定快指针 fast 慢指针 slow 初始值为链表的头。设入环前的距离为 x 。当 slow 走了 x/2 时fast 入环。fast 走了一段路程后slow 入环fast 开始追击 slow最后 fast 和 slow 相遇。
而这里面的走法和之前的一篇博客中求链表的中间节点的方法一样。奇数节点走到最后一个节点偶数节点走到空。如果走到这两个条件说明链表一定不带环。否则不会走到空它们一定会相遇为环形链表。
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
bool hasCycle(struct ListNode *head)
{struct ListNode *fast,*slow;fastslowhead;while(fastfast-next){slowslow-next;fastfast-next-next;if(fastslow){return true;}}return false;
}2. 环形链表延伸问题
2.1 问题1
“为什么 slow 和 fast 指针一定会在环中相遇会不会错过永远追不上请证明一下”
一slow 和 fast fast 一定是先进环。这时 slow 走了入环前距离的一半。
二随着 slow 进环fast 已经在环里走了一段了。走了多少跟环的大小有关。
假设 slow 进环时slow 和 fast 的距离是 N。N 的长度一定小于环。fast 开始追 slow slow 每次往前走 1 步fast 往前走 2 步。每追一次判断一下是否相遇。
每追 1 次fast 和 slow 的距离变化N - N - 1 - N - 2 … 1 - 0.
N
N - 1
N - 2
N - 3
…
1
0
可以追上 每追 1 次距离减少 1 。它们最后的距离减到 0 时就是相遇点。 总结 快指针走两步一定会追到慢指针
2.2 问题2
“为什么 slow 走一步fast 走两步能不能 fast 一次走 n 步 (n 2) 请证明一下”
假设我们 slow 走一步fast 走三步。
它们之间的 距离变化 如下
N 是偶数 N 是奇数
N N
N - 2 N - 2
N - 4 N - 4
N - 6 N - 6
… …
2 1
0 -1
可以追上 这一次追不上注意: N 是 fast 和 slow 之间的距离。
2.2.1 当 N 是 奇数
如果 fast 走 3 步 slow 走 1 步一个周期是肯定追不上的。走到最后它们之间的距离变为 -1 意味着现在 fast 在 slow 前面一步它们之间的距离变为 c - 1 。c 是环的长度
而长度一旦为 c-1 就有会引申出两种情况看下图
我们这里已经 初步证明 了当 fast 一次走 n(n 2) 步时fast 是不一定可以追上 slow 的。
2.2.1 当 N 是 偶数
假设 fast 一次走 4 步slow 一次走 1 步。
N 是 3 的倍数 N 不是 3 的倍数(N是 1 的倍数) N 不是 3 的倍数(N 是 2 的倍数)
N N N
N - 3 N - 3 N - 3
N - 6 N - 6 N - 6
N - 9 N - 9 N - 9
… … …
3 2 1
0 -1 -2
可以追上 这一次追不上 这一次追不上假设 c 是环的长度。 -1 意味着距离是 c - 1-2 意味着距离是 c - 2。 如果 c - 1 和 c - 2 是 3 的倍数就可以追上否则就追不上。
结论fast 走 2 步slow 一定可以追上因为它们的距离逐次减 1 。但是当 n 2 时不一定会相遇。
3. 环形链表 II
链接142. 环形链表 II
描述 给定一个链表的头节点 head 返回链表开始入环的第一个节点。 如果链表无环则返回 null。
如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。如果 pos 是 -1则在该链表中没有环。注意pos 不作为参数进行传递仅仅是为了标识链表的实际情况。 不允许修改 链表。 示例1: 输入head [3,2,0,-4], pos 1 输出返回索引为 1 的链表节点 解释链表中有一个环其尾部连接到第二个节点。 示例2 输入head [1,2], pos 0 输出返回索引为 0 的链表节点 解释链表中有一个环其尾部连接到第一个节点。 示例3 输入head [1], pos -1 输出返回 null 解释链表中没有环。 提示 链表中节点的数目范围在范围 [0, 10^4] 内 -10^5 Node.val 10^5 pos 的值为 -1 或者链表中的一个有效索引
既然是要求 链表的入环点那么用 环形链表 的方法找到 交点 在之前的一篇博客里有个叫做 相交链表 的问题我把这个 入环的第一个节点 看作是 两个相交链表的尾结点 把起始点和相遇点的下一个节点分别作为两链表的头节点就转换成了链表相交的问题于是又一次运用了 快慢指针。
3.1 思路1相交链表 先利用 快慢指针 以 环形链表 的解法找到 fast 和 slow 相交的点。然后将这个 交点 给为 meetnode 。作为两条新链表的尾。那么 meetnode-next 为某条新链表的头。然后 入环点 就可以看做是两条链表的交点。然后就是 相交链表 的做法
代码
struct ListNode *detectCycle(struct ListNode *head)
{struct ListNode* fast, *slow;fast slow head;struct ListNode* tail NULL;while (fast fast-next){slow slow-next;fast fast-next-next;// 相遇if (fast slow){tail slow;break;}}// 没有相遇if (tail NULL){return NULL;}struct ListNode* newHead tail-next;int lenH 1, lenN 1;struct ListNode* curH head, *curN newHead;while (curH ! tail){lenH;//LXcurH curH-next;}while (curN ! tail){lenN;//CcurN curN-next;}struct ListNode* longList lenH lenN ? head : newHead;struct ListNode* shortList lenH lenN ? newHead : head;int gap abs(lenH - lenN);while (gap--)//让长的先走相差步数{longList longList-next;}while (longList ! shortList){longList longList-next;shortList shortList-next;} return longList;
}3.1 思路2公式推导
这个方法的难点在于公式推导的过程只要推导出了公式解题就变得十分简单 结论一个指针从 相遇点 开始走一个指针从 链表头 开始走它们会在 环的入口点 相遇。” 接下来推导公式 由于 fast 的速度是 slow 的 2 倍。
所以便可以得出这个式子2 ( L x ) L N * c x而这个式子又可以进行推导
2 ( L x ) L N * c x↓L x N * c↓L N * c - x↓L ( N - 1 ) * c c - x 这里 公式已经推导 完成L ( N - 1 ) * c c - x 。但是这个公式到底是什么意思 意思是一个指针从起始点开始走一个指针从相遇点开始走它们会在环的入口点相遇 根据这个我们也就可以做出这道题目了。
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode *detectCycle(struct ListNode *head)
{struct ListNode *fast,*slow;fastslowhead;struct ListNode*tailNULL;while(fastfast-next){slowslow-next;fastfast-next-next;if(fastslow){struct ListNode *meetNodeslow;while(meetNode!head){headhead-next;meetNodemeetNode-next;}return meetNode;}}return NULL;
}4. 复制带随机指针的链表
链接138. 复制带随机指针的链表
描述 给你一个长度为 n 的链表每个节点包含一个额外增加的随机指针 random 该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如如果原链表中有 X 和 Y 两个节点其中 X.random - Y 。那么在复制链表中对应的两个节点 x 和 y 同样有 x.random - y 。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示 val一个表示 Node.val 的整数。 random_index随机指针指向的节点索引范围从 0 到 n-1如果不指向任何节点则为 null 。 你的代码 只 接受原链表的头节点 head 作为传入参数。 示例1 输入head [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出[[7,null],[13,0],[11,4],[10,2],[1,0]] 示例2 输入head [[1,1],[2,1]] 输出[[1,1],[2,1]] 示例3 输入head [[3,null],[3,0],[3,null]] 输出[[3,null],[3,0],[3,null]] 提示 0 n 1000 -10^4 Node.val 10^4 Node.random 为 null 或指向链表中的节点。
通过分析这个链表结构应含有 三个成员
struct Node
{int val;struct Node* next; // 下一个节点的地址struct Node* random; // 指向随机节点的指针
};看到复制两字可能会想“这不是只要复制原链表的每个节点将其链接起来不就行了。 但仔细一想 random 呢这个怎么复制 题目里说了它是 深拷贝 那么就应该完全复刻啊并且即使知道了原链表中和 random 链接的节点也不知道 random 和它的相对位置那应该如何做呢
4.1 思路
可以在原链表中每个节点的后面复制这个节点插入到原节点和下一个节点之间 就相当于我知道 复制的节点是在原节点的后面 如果我已经知道原节点的 random 那么我 复制节点的 random 不就是 原节点的random的next节点再将 复制节点 链接为新链表和原链表断开链接恢复原链表就可以了
4.1.1 在原节点后插入复制节点 首先我们给定一个 copy 节点。在原链表每个节点的后面和这个节点的下一个节点之间插入 copy 节点。
这里就对细节有一定的要求。我们就把遍历原链表的节点叫做 cur 吧。
如果 cur 为空则不进行拷贝。我们插入的 copy 节点是 动态开辟 的。我们需要将 copy 链接到 cur-next 然后在让 cur-next 给定为 copy 。随后 cur 就需要原节点的后方也就是当前 copy 节点的 next 。这就考察了 任意插入元素。
4.1.2 根据原节点的random处理复制节点的random 其实我们现在已经将 copy 节点和 原链表建立了联系。
原链表的 random 为 cur-random 、而我们插入的 copy 节点也需要链接。如果我们原链表的当前节点的 random 为 cur-random 那么我的 copy 节点的 random 节点的相对位置应该和当前节点相同。而我们的当前节点的 random 的后方的 拷贝节点 就是这个 copy 节点的 random 。那么我 copy-random 就等于 cur-random-next 。这样不就链接起来了
这过程中只要处理好迭代关系就可以了但是需要注意当 random 指向为 NULL 时拷贝处也为 NULL。
4.1.3 复制节点链接为新链表原节点恢复 完成这一步我们需要 copyhead 和 copytail 作为复制链表的头和尾。
而复制节点链接为新链表的过程实际上就是 尾插 。所以要注意一下 空链表尾插 和 正常尾插 的情况。
并且在这过程中将原链表的链接逐渐恢复。
代码
/*** Definition for a Node.* struct Node {* int val;* struct Node *next;* struct Node *random;* };*/
struct Node* copyRandomList(struct Node* head)
{struct Node* cur head;// 1. 在原节点后插入复制节点while (cur){// 插入复制节点struct Node* copy (struct Node*)malloc(sizeof(struct Node));copy-val cur-val;copy-next cur-next;cur-next copy;// cur往后迭代cur copy-next;}// 2. 根据原节点的random处理复制节点的randomcur head;while (cur){// copy节点在cur的后面struct Node* copy cur-next;if (cur-random NULL){copy-random NULL;}else{copy-random cur-random-next;}cur copy-next;}// 3. 复制节点链接为新链表原节点恢复struct Node* copyHead NULL, *copyTail NULL;cur head;while (cur){struct Node* copy cur-next;struct Node* next copy-next;// 记录原链表的下一个节点// 复制节点链接为新链表(本质为尾插)if (copyTail NULL){copyHead copyTail copy;}else{copyTail-next copy;copyTail copy;}cur-next next;// 恢复链接cur next;}return copyHead;
}5.总结
今天我们分析并完成环形链表相关OJ题也学习和了解环形链表延伸问题通过分析明白了底层原理愿这篇博客能帮助大家理解这些OJ题因为环形链表系列问题是十分经典的面试题。希望我的文章和讲解能对大家的学习提供一些帮助。到这里链表OJ题系列也就到此收官了。之后会继续更新数据结构的相关知识点。 当然本文仍有许多不足之处欢迎各位小伙伴们随时私信交流、批评指正我们下期见~
