浏阳建设局网站,微信公众号人工服务电话,wordpress下划线,wordpress是英文版的W...Y的主页 #x1f60a;
代码仓库分享 #x1f495; 前言#xff1a; 今天是链表顺序表OJ练习题最后一次分享#xff0c;每一次的分享题目的难度也再有所提高#xff0c;但是我相信大家都是非常机智的#xff0c;希望看到博主文章能学到东西的可以一键三连关注一下博主…
W...Y的主页
代码仓库分享 前言 今天是链表顺序表OJ练习题最后一次分享每一次的分享题目的难度也再有所提高但是我相信大家都是非常机智的希望看到博主文章能学到东西的可以一键三连关注一下博主。
话不多说我们来看今天的OJ习题.。 【leetcode 142.环形链表II】 OJ链接 给定一个链表的头节点 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
解释链表中没有环。 题目函数接口 head目标链表 分析在上一篇博客中我们讲述了如何寻找相遇点创建两个指针slow与fastfast的速度为slow的两倍最终会在环中追及到。 下面讲述的方法与昨天的有关联 slow进入环后只会走不到一圈就会被fast追上如果L足够长环足够小fast会在环中走n圈n1。 我们分析完题目就会迎刃而解。我们只需要先找到相遇点然后一个指针从起点走一个指针从相遇点走它们相遇后的地址就是我们要的答案 代码演示 struct ListNode *detectCycle(struct ListNode *head) {struct ListNode *fast head;struct ListNode *slow head;while(fast fast-next){fast fast-next-next;slow slow-next;if(fast slow ){struct ListNode *cur head;while(cur ! slow){cur cur-next;slow slow-next;}return slow;}}return NULL;
} 再给大家提供一种思路 思路二我们可以先找到相遇点然后将环从相遇点截断这个链表就变成了相交链表然后找到相交链表的相交点即可。 这个想法很简便也很大胆不知道相交链表已经做题方法的可以在顺序表链表OJ题(2)-【数据结构】中找到相交链表的介绍以及相关题型。 struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {int lena 1;int lenb 1;struct ListNode *cura headA;struct ListNode *curb headB;while(cura-next){cura cura-next;lena;}while(curb-next){curb curb-next;lenb;}if(cura ! curb){return NULL;}int gap abs(lena-lenb);struct ListNode *llist headA;struct ListNode *slist headB;if(lena lenb){;}else{llist headB;slist headA;}while(gap--){llist llist-next;}while(llist ! slist){llist llist-next;slist slist-next;}return llist;
}
struct ListNode *detectCycle(struct ListNode *head) {struct ListNode *fast head;struct ListNode *slow head;while(fast fast-next){fast fast-next-next;slow slow-next;if(fast slow){struct ListNode *meet slow;struct ListNode *newhead meet-next;meet-next NULL;return getIntersectionNode(newhead, head);}} return NULL;
} 【leetcode 138.复制带随机指针的链表】 OJ链接 给你一个长度为 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]] 题目函数接口 head目标链表 这道题比较复杂拷贝一般链表非常简单但是这个链表比较特殊在结构体中加入了随机指针如果我们先将无random指针链表拷贝一份再去寻找random指针在链表中指向的位置会非常麻烦我们必须不停遍历链表时间复杂度就非常高O(n^2)。而且代码也会非常的复杂不建议使用暴力解法。 现在唯一难点就是如何找到新链表中random对应的位置因为创建新链表与目标链表的地址是没有任何关联的。 但是接下来的方法相对于暴力解法会非常轻松这个想法也是非常新颖的 思路 我们在原链表中每个结构体的后面插入新的结构体将对应的内容拷贝到插入的新结构体中就是这样 这样我们就可以很方便的寻找random创建一个指针copy就比如上图中的13节点我们需要拷贝13中的random到后面连接的新结构体中只需要找到旧结构体中random指向的内容让旧结构体的next的next-random等于copy指向的random即可。 最后一步只需要将完全拷贝好的新结构体拿下来尾插组成一个新链表即可完成 理论形成时间开始 struct Node* copyRandomList(struct Node* head) {struct Node*cur head;while(cur){struct Node*next cur-next;struct Node*copy (struct Node*)malloc(sizeof(struct Node));copy-val cur-val;cur-next copy;copy-next next;cur next;}cur head;while(cur){struct Node*copy cur-next;if(cur-random NULL){copy-random NULL;}else{copy-random cur-random-next;}cur copy-next;}cur head;struct Node*copyhead NULL;struct Node*copytail NULL;while(cur){struct Node* copy cur-next;struct Node* next copy-next;if(copytail NULL){copyhead copytail copy;}else{copytail-next copy;copytail copytail-next;}cur-next next;cur next;}return copyhead;
} 新节点插入老节点中、copy指针的寻找新链表……都需要我们画图更好的理解。 这两道题都是想法比较前卫一般方法比较困难的题虽然用c语言比较麻烦但是等到后面我们掌握了map以及哈希结构就会非常简单。
以上就是本次OJ题目的全部内容希望大家看完有收获一键三连支持一下博主吧
