3d演示中国空间站建造,搜索引擎营销的缺点,用wordpress 扒站,百度关键词优化费用双指针//哈希表 解决链表有环等问题 19. 删除链表的倒数第N个结点遍历两次#xff0c;先求得链表长度#xff0c;再删除双指针#xff0c;只遍历一次 141. 环形链表 【判断链表是否有环】哈希表快慢双指针 142. 环形链表Ⅱ 【找环的入口】哈希表双指针求环中有多少个结点 面… 双指针//哈希表 解决链表有环等问题 19. 删除链表的倒数第N个结点遍历两次先求得链表长度再删除双指针只遍历一次 141. 环形链表 【判断链表是否有环】哈希表快慢双指针 142. 环形链表Ⅱ 【找环的入口】哈希表双指针求环中有多少个结点 面试题02.07. 链表相交哈希表双指针思路Ⅰ思路Ⅱ 19. 删除链表的倒数第N个结点
题目链接19. 删除链表的倒数第N个结点 题目内容
如果把链表换成数组等数据结构可以直接根据下标从数组末端开始找到倒数第N个元素。但是链表的缺点就在于查找元素的时候需要O(N)的时间复杂度。由于其结点都是通过前驱结点的next指针连接的单向链表中因此只能一个方向遍历链表结点不能直接从后往前找到倒数第N个。
遍历两次先求得链表长度再删除
从前往后如何找到倒数第N个结点呢假设链表长度为Size那么倒数第N个结点实际上就是正数第Size1-N个结点。【比如Size5N2倒数第2个结点是正数第4个结点Size-1N4】。由此可以想到最直接的办法遍历两次链表第一遍求得Size第二遍定位到要删除的结点并删除。 实际上删除结点需要将待删除结点的前驱结点和后驱结点连接起来因此找到前驱结点就行。 从head开始找到第Size-N个结点即为待删除结点的前驱节点。 代码实现C
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {int Size 0;//构建一个虚拟头节点不需要单独讨论删除头节点的情况ListNode *dummyhead new ListNode(0, head);ListNode *currNode dummyhead-next;//统计链表长度【除虚拟头节点外的结点数】while(currNode){Size;currNode currNode-next;}currNode dummyhead;//定位到要删除结点的前驱结点 第Size-N个结点for(int i 0; i Size - n; i){currNode currNode-next;}//要删除的结点是currNode-nextListNode *tmp currNode-next;//将待删除结点tmp的前驱结点和后驱结点连接起来currNode-next tmp-next;delete tmp;return dummyhead-next;}
};双指针只遍历一次
解决这道题目的重点是知道倒数第N个结点实际上就是正数的第Size1-N个结点。问题在于是否需要求得Size呢 如果不求Size怎么能够找到第Size1-N个结点呢 使用双指针一个slow一个fast。先让fast向前定位到第n个结点之后slow从第一个结点开始fast从第n个结点开始slow和fast都每次向前移动一个结点直到fast-next null【即移动到链表最后一个结点相当于定位到了第Size个结点fast从第n个结点走到第Size个结点走了Size-n步slow从第1个结点就走到了Size-n1个结点】slow对应的结点就是要删除的结点。 在实际代码中增加一个虚拟头结点这样删除头结点的情况就不需要单独处理。slow从虚拟头结点开始移动Size-n次相当于移动到了被删除结点的前面一个结点【如果是一定要移动到被删除结点那么终止条件改成fastnull即可这样相当于fast从第n个结点移动到Size1的位置走了Size1-n次slow刚好走到Size1-n结点的位置】。下图讨论了没有虚拟头节点和有虚拟头节点slow最终指向待删除结点和待删除结点前面一个结点的情况
以下代码C实现的是上图的第二种情况即有附加头节点slow指向的待删除结点的前驱节点
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode *dummyhead new ListNode(0, head); //新建虚拟头节点ListNode *slow dummyhead, *fast dummyhead;//fast先指向第n个结点while(n){fast fast-next;n--;}//fast指向最后一个结点结束while(fast-next){fast fast-next;slow slow-next;}//fast指针没用了用来保存待删除的结点fast slow-next;//建立新的连接slow-next fast-next;delete fast; //删除结点return dummyhead-next;}
};141. 环形链表 【判断链表是否有环】
题目链接环形链表 题目内容 根据题意实际上就是判断链表中是否存在环。
哈希表
遍历链表并将各个结点地址存入一个unordered_set中如果某个地址在set中出现过即可认为有环。
class Solution {
public:bool hasCycle(ListNode *head) {if(head nullptr || head-next nullptr)return false;unordered_set ListNode * visited; //用来存访问过的结点地址ListNode *currNode head; //从head结点开始遍历while(currNode){if(visited.count(currNode)) //如果当前结点地址已经访问过了即有环return true; visited.insert(currNode); //否则添加到set中currNode currNode-next;//结点后移}return false;}
};快慢双指针
经典的Floyd判圈算法。一个slow指针一个fast指针。slow从头节点开始每次向前移动一个结点fast从头节点开始每次向前移动两个结点
如果没有环fast因为移动更快而先遍历完链表如果fastnull || fast-next null即可认为没有环如果有环那么fast只是比slow更先进入环内绕圈待slow也进入环内fast每次在圈内走两步slow走一步fast和slow之间的距离就减少一步最后fast最追上slow即出现fast slow即可判断有环。
代码如下C
class Solution {
public:bool hasCycle(ListNode *head) {if(head nullptr) return false; ListNode *slow head, *fast head;while(fast ! nullptr fast-next !nullptr ){slow slow-next;fast fast-next-next; if(slow fast) //fast追上了slow有环return true;}//退出循环是因为fast先遍历完链表无环return false;}
};
142. 环形链表Ⅱ 【找环的入口】
题目链接142. 环形链表Ⅱ 题目内容 理解题意实际上就是在判断链表是否有环的基础上找出进入环的第一个结点
哈希表
同样使用哈希表和141题的判断是否有环一样用set存各个结点的地址如果出现了重复的地址那么第一次重复的就是环的入口
class Solution {
public:ListNode *detectCycle(ListNode *head) {if(head nullptr || head-next nullptr)return nullptr;unordered_set ListNode * visited;ListNode *currNode head;while(currNode){if(visited.count(currNode))return currNode; //第一次重复的地址就是环的入口visited.insert(currNode);currNode currNode-next;}return nullptr;}
};双指针
这里涉及到一些数学推理了……依旧是slow、fast两个指针从头节点开始请看下图 这里的x、y、z表示某一段链表中的节点数都是左开右闭的即起始结点不包括终止结点包括【这个很重要的】。x从头节点开始到环入口结点的结点数量yslow结点进入环以后即从入环节点开始移动y个节点slow和fast相遇z从slow和fast相遇节点开始slow或fast要移动z个节点到达入环节点。 接下来分析x、y、z之间的数学关系slow和fast相遇时
fast先进入环开始绕圈【假设绕了n圈才和slow相遇n≥1】所以fast已经遍历的节点数xyz*nyslow后进入环入环后第一圈移动y个节点就和fast相遇了slow遍历的节点数xy;【这里肯定是第一圈没走完就能和fast相遇的因为slow入环的时候fast在环中一个位置slow在入环节点处假设fast距离入环节点m个节点的话也就是和slow相差m个节点的距离之后每一次移动fast向slow靠近一个节点那么移动m次就相遇即题目中的y。m肯定是小于环的节点数的。】
因为fast每次向前移动两个slow每次移动一个所以2*(xy) xn*(yz)y等式处理一下就得到了x (n-1)*(yz) z如果n1xz即index1指针从head开始index2指针从slow与fast相遇的节点开始两个分别向前移动移动相同次数index1和index2会相遇相遇处即为入环处如果n1就是index2在环内绕了(n-1)圈后和index1在入环处相遇。总之就是index1和index2会相遇相遇处就是入环处。代码如下C
class Solution {
public:ListNode *detectCycle(ListNode *head) {if(head nullptr || head-next nullptr)return nullptr;ListNode *slow head, *fast head;//fast和slow都从头节点开始do{if(fast fast-next){slow slow-next;fast fast-next-next;}elsereturn nullptr; //如果fast先遍历完链表即没有环}while(slow ! fast); //跳出循环即为有环slow head; //slow从head开始fast从相遇点开始//二者每次向前移动一个节点相遇处即为入环处while(slow ! fast){slow slow-next;fast fast-next;}return slow; }
};求环中有多少个结点
上面已经分析了环中结点有yz【假设xy n】个实际上不需要单独去求y和z。slow和fast相遇之后fast走两圈slow走一圈重新在原来的地方相遇。即相遇点一直是一样的。 为什么呢slow和fast相遇可以看作fast和slow之间差了n个结点每次fast走两步slow走一步两个之间的距离拉近一步所以需要走n步二者重新相遇。slow走n步就是一圈回到之前相遇的地方fast走n步就是走了两圈回到之前相遇的地方。因此相遇点一直是第一次相遇的地方且每次都是fast走两圈slow走一圈后相遇【除第一次】。所以从第一次相遇开始找到了相遇点slow第二次走到这个点走过的节点数就是环中的节点数。
面试题02.07. 链表相交
题目链接面试题02.07. 链表相交 题目内容 理解题意判断两个链表有没有相交的部分。
哈希表
如果两个链表相交那么从相交节点开始之后的节点都是公共的是相同的地址。所以还是可以用哈希表解决先遍历其中一个链表然后将其每个节点的地址存入set中之后遍历第二个链表并判断每个节点地址是否在set中如果在那么直接返回这个地址就是相交起始节点。如果遍历完第二个链表都没有公共的节点地址那么就是不相交的。代码如下C
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {unordered_set ListNode * visited;ListNode *currNode headA;while(currNode){ //遍历第一个链表并将各个节点的地址存在set中visited.insert(currNode);currNode currNode-next;} currNode headB;while(currNode){//遍历第二个链表并判断每个节点地址是否出现在set中if(visited.count(currNode))return currNode; //找到相交起始点currNode currNode-next;}return nullptr;}
};双指针
按道理遍历两个链表的同时对比是否有相同的节点地址就能直到是否有交叉部分。但是问题在意两个链表长度不一样如果都从头开始遍历的话即便两个链表是相交的但是由于对比的节点没有对齐而结果不正确。 所以解决办法是怎么把两个链表对齐。
思路Ⅰ
两个链表相交从相交点开始到末尾节点的都是重合的。在相交节点之前链表A有几个节点、链表B有几个节点都不重要也不确定。所以就是把两个链表按尾节点对齐。先遍历链表A和B统计两个链表的节点数【假设为Size_A和Size_B】节点数大的链表先移动max(Siez_ASize_B) - min(Size_ASize_B)个节点与节点数小的链表的头节点对齐【也相当于是为按尾节点对齐】之后逐个对比两个链表的结点的地址。 代码如下C
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {//统计两个链表中的节点数int len_A 0, len_B 0;ListNode *currNodeA headA, *currNodeB headB;while(currNodeA){ //统计链表Alen_A;currNodeA currNodeA-next;}while(currNodeB){//统计链表Blen_B;currNodeB currNodeB-next;}//从新从头开始遍历两个链表currNodeA headA;currNodeB headB;while(len_A len_B){ //如果Len_A更大进入这个循环currNodeA currNodeA-next;len_A--;}while(len_B len_A){//如果len_B更大进入这个循环currNodeB currNodeB-next;len_B--;}//两个链表已经对齐了开始逐个结点对比while(currNodeA currNodeB){if(currNodeA currNodeB)return currNodeA;currNodeA currNodeA-next;currNodeB currNodeB-next;}return nullptr;}
};思路Ⅱ
虽然两个链表长度不一样不能对齐那么把链表A和链表B拼起来呢即一个指针currNodeA先遍历链表A遍历完链表A后从头开始遍历链表B另一个指针currNodeB先遍历链表B遍历完链表B后从头开始遍历链表A。 那么currNodeA和currNodeB都遍历两个链表如果链表A和链表B有相交部分currNodeA和currNodeB就会相等且不为null如果没有相交的部分currNodeA和currNodeB最后就遍历完链表均为null。 代码实现如下C
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode *currNodeA headA, *currNodeB headB;while(currNodeA ! currNodeB){if(currNodeA)currNodeA currNodeA-next;else currNodeA headB;if(currNodeB)currNodeB currNodeB-next;elsecurrNodeB headA;}return currNodeA;}
};
