宁波网站建设哪家公司好,库尔勒网站建设,中国建筑考试网入口,网站建设平台多少钱目录 文章目录 前言 1. 题目一#xff1a;环形链表Ⅱ 1.1 思路 1.2 分析 1.3 题解 1.4 方法二 2. 题目二#xff1a;复制带随机指针的链表 2.1 思路 2.2 分析 2.3 题解 总结 前言 在这个专栏博客中#xff0c;我们将提供丰富的题目资源和解题思路#xff0c;帮助读者逐步提… 目录 文章目录 前言 1. 题目一环形链表Ⅱ 1.1 思路 1.2 分析 1.3 题解 1.4 方法二 2. 题目二复制带随机指针的链表 2.1 思路 2.2 分析 2.3 题解 总结 前言 在这个专栏博客中我们将提供丰富的题目资源和解题思路帮助读者逐步提高解题能力。同时我们也将分享一些刷题技巧和经验帮助读者更加高效地进行刷题训练。通过持之以恒的努力和不断的实践相信读者可以在数据结构领域取得长足的进步。本期将是数据结构刷题训练链表篇的最后一期后续我们将进入栈和堆的刷题训练。 1. 题目一环形链表Ⅱ
题目描述 示例 题目链接环形链表Ⅱ
1.1 思路 本题的题意是给定一个链表返回链表开始入环的第一个节点。 如果链表无环则返回 NULL。 寻找第一个入环的节点在上道环形链表的题目中仅仅只是判断是否有环但没法确定入环的节点这道题目属于之前题目的进阶。那我们要如何去解决呢 这里向大家说明一点如果在刷题的时候遇到一个题目连题意都很难理解或者是无从下手那这道题目就不再是简简单单的考察代码能力其中的分析更为重要没有分析的过程仅仅只要代码是无法看懂理解的。
1.2 分析 初看题目毫无思路但是别担心我在分析之后记住这种做题思路、方法就可以在后续刷题中灵活运用。这道题目我们仍然可以使用快慢指针的方法。 首先我们需要知道带环链表的几种情况
一般情况 环很大 环很小 在上期中我们将道使用快慢指针遍历链表快指针一次走两步慢指针一次走一步如果它们相遇那它们一定是带环的链表。那问题来了fast一次走两步slow一次走一步一定可以追上吗 结论是一定能追上。 为什么我们可以分析一下在两个指针都入环以后快指针一次走两步慢指针一次走一步它们的距离会减一一直走一直减一最后直到追上距离变化过程 N N-1 N-2 …… 2 1 0 那如果fast一次走3步slow一次走两步呢 假设它们之间的距离是Mfast和slow都进环以后它们的距离一次就是减2那它们的距离变化 M是偶数 M是奇数 M-2 M-2 M-4 M-4 …… …… 4 3 2 1 0 -1 如果M是偶数就刚好追上相遇如果M是奇数这就说明它们会错过一旦错过就要继续走一圈假设环的周长是C当C为奇数时当它们错过后它们之间的距离是C-1此时C-1必为偶数下次一定能追上但如果C是偶数时C-1为奇数然而它们每次距离减小2这样无论怎么走都不会相遇。 如果继续增大步数呢fast一次走4步slow一次走两步。假设进入环后它们的距离是k那么它们的距离变化 k是3的倍数 k%32 k%31 k-3 k-3 k-3 k-6 k-6 k-6 …… …… …… 6 5 4 3 2 1 0 -1 -2 错过后距离 C-1 C-2 如果C-1或C-2仍然不是3的倍数那它们仍然始终无法相遇。有人可能会这样想那让其中一个停下来另一个去追不就可以了但我们无法确定慢指针是否进环了如果没进环那快指针走多少圈都不会追上。这里只是移动步数的分析在带环链表中使用快慢指针最好使用步数差为1的下面步入正题 依据上述结论我们看这道题目这里我们让fast一次走2步slow一次走1步当fast入环时 假设从起点到入环点距离为L环周长为C 慢指针入环时 相遇时 由上可以得出fast走的距离时slow的二倍那slow走的距离就是XL那fast走的路程就是LXn*Cn0因为无法确定L于C的关系如果C很小那fast就可能走了很多圈。或许有人会疑惑那slow为什么不用加n*C因为slow入环以后fast在slow走一圈之内一定能追上它。 我们根据这些关系可以得到 LXn*C2LX 化简一下 LXn*C n*C-XL 得到n*C-XL这个结论再转化一下就是(n-1)*CC-XL 到这里就一目了然了一个指针从相遇点开始出发一个从起点开始出发最终它们会在入环点相遇。
1.3 题解
根据上述的分析进行编写代码
struct ListNode *detectCycle(struct ListNode *head)
{struct ListNode* slow,*fast;slowfasthead;while(fastfast-next){slowslow-next;fastfast-next-next;if(slowfast){struct ListNode* meetslow;while(meet!head){headhead-next;meetmeet-next;}return head;}}return NULL;
}
1.4 方法二 方法二的思路简单但代码量增多我们先让两指针相遇相遇后将相遇的节点的next置为NULL也就是将环断掉这样就转化成了链表相交。 代码如下
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{struct ListNode* curAheadA,*curBheadB;int lenA1,lenB1;while(curA-next){curAcurA-next;lenA;}while(curB-next){curBcurB-next;lenB;}if(curA!curB){return NULL;}int t abs(lenA-lenB);struct ListNode* longlistheadA, *shortlistheadB;if(lenBlenA){longlistheadB;shortlistheadA;}while(t--){longlistlonglist-next;}while(longlist!shortlist){longlistlonglist-next;shortlistshortlist-next;}return longlist;
}
struct ListNode *detectCycle(struct ListNode *head)
{struct ListNode* slow,*fast;slowfasthead;while(fastfast-next){slowslow-next;fastfast-next-next;if(slowfast){struct ListNode* meetslow;struct ListNode* newnodemeet-next;meet-nextNULL;return getIntersectionNode(newnode,head);}}return NULL;
}
2. 题目二复制带随机指针的链表 题目描述 示例 题目链接
复制带随机指针的链表
2.1 思路 或许大部分人读完题目还是像上道题目一样读完没有思路甚至连题意都读不懂。 复制一个链表不难但这道题目的难点在于每个节点指针域的随机指针我们很难控制随机指针的指向单纯的完全复制行不通复制下来的节点关系要与原链表相同这才是本道题目的难点。
怎么才能找到随机指针的指向关系呢
我们的思路是这样的
遍历原链表遍历一个节点复制一个节点然后将复制的节点插入道原节点的后边。再次遍历插入后的链表找复制节点的随机指针的指向关系。最后将复制的链表与原链表分开
2.2 分析 根据思路进行分析 复制后的链表链接道原链表 这里要理解如何去找复制节点的random指向的节点。
我们可以这样操作copy-randomcur-random-next 重点就是这句的理解cur指向的是原链表中的节点复制的也就是cur指向的节点然后将复制的节点copy链接到cur节点后那copy节点的random不就在cur节点的random指向节点的下一个吗 意思就是说遍历原链表中的节点找到当前节点的random就可以找到复制节点的random因为复制节点copy的random就是当前节点原链表random指向节点的下一个节点。 这里要好好理解例如13号这个节点cur)13节点的下一个节点就是复制的13号节点。cur的random指向的是7号节点原链表7号节点的下一个节点不就是复制的13号节点copy要找的random吗 但这里需要特殊处理一种情况就是原链表random指向为NULL的情况这里就直接将复制节点的random置为NULL。
2.3 题解
根据上述的分析开始编写代码
struct Node* copyRandomList(struct Node* head)
{struct Node* curhead;while(cur) //复制节点{struct Node* copynode(struct Node*)malloc(sizeof(struct Node));struct Node* nextcur-next;copynode-valcur-val;//插入到原节点后cur-nextcopynode;copynode-nextnext;curnext;}curhead;//寻找复制节点的randomwhile(cur) {struct Node* copynodecur-next;if(cur-randomNULL) //随机指针为NULL进行特殊处理{copynode-randomNULL;}else{copynode-randomcur-random-next;}curcur-next-next;}curhead;struct Node* copyhead,*copytail;copyheadcopytailNULL;//还原原节点将两个链表分开while(cur){struct Node* copynodecur-next;struct Node* nextcur-next-next;//将复制节点链接到新的链表这里使用的是无头节点的链表所有需要特殊处理if(copyheadNULL){copyheadcopytailcopynode;}else{copytail-nextcopynode;copytailcopytail-next;}//恢复原链表cur-nextnext;curnext;}return copyhead;
} 总结 本期的题目相对较为复杂希望大家能够好好的消化理解最后感谢你的阅读和支持。希望你在这个数据结构的学习旅程中能够获得满满的收获和成就感。愿我们共同努力不断探索和挑战成为数据结构领域的行家里手
