本网站仅支持ie浏览器,多语言网站 推广,福州seo按天扣费,全球互联网企业100强名单1、找公共节点
延伸问题#xff1a;
1、为什么一定会相遇#xff1f;不会追不上吗#xff1f; 假设slow进环时#xff0c;fast与slow之间的距离是N#xff0c;两者之间的距离每次运动缩小一#xff0c;一定会出现N 0 的情况#xff0c;所以一定会相遇
2、那么可以fa…1、找公共节点
延伸问题
1、为什么一定会相遇不会追不上吗 假设slow进环时fast与slow之间的距离是N两者之间的距离每次运动缩小一一定会出现N 0 的情况所以一定会相遇
2、那么可以fast指针一次走三步吗四步可以吗n步呢
令slow进环时两者之间的距离为N, 链表的环的大小是C在进环以前链表的长度是L。 对于走两步而言两者之间的相对速度是二这时候进行分类讨论若链表的环的大小是偶数则会陷入死循环最后走完每一轮fast都比slow快一步 但实际上分析死循环的条件是N为奇数C为偶数。 当slow刚好进环时设fast在这里已经走了x圈fast指针在这里走的路程是L x * C C - Nslow指针在这里走的路程是L两者存在关系3*L L x * C C - N即2*L x1*C -N;
但是若C为奇数而N为偶数则上式一定不成立所以一定能够相遇 至于其他走法都是同一种思路走几步没关系关键的是他们之间的速度差不过越往后需要分类讨论的情况越复杂
3、给定一个链表请判断他是否有环若有环则返回环的起始节点若没有环则返回NULL 链表以前的大小是L环的大小是Cslow入环时两者之间的距离是N slow走的路程一定是小于C的因为slow每走一步两者之间的距离都小一而两者间最大距离最大就是C不等于所以slow只走环的一部分就追上了 设slow到达环时fast一走x圈。 相遇时slowLNfastLx*CN 故2*LN Lx*CN 即Lx*C-N 这里可以理解为先让我们的meet指针回到我们的环的起点位置-N此后再让他走x圈x*C在某次他走完一圈以后从head开始的cur指针就也到达了环的起点而这时meet也在起点两者相遇。
具体代码实现如下
typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head) { ListNode* fast head; ListNode* slow head; ListNode* meet NULL; ListNode* cur head; int flag 0; while(fast fast-next) { fast fast-next-next; slow slow-next; if(fast slow) { meet fast; flag 1; break; }//这里要先进行判断 } if(flag 0) { return NULL; } else { while(cur ! meet) { cur cur-next; meet meet-next; } return cur; }
}
或者也可以让meet-next Newhead, 再将meet-next置为空从而转化为求公共节点问题 找公共节点如下····························
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) { //还是要用快慢指针解决 //当快指针进环的时候慢指针还在中间slow进环以后开始追击 //若不带环fast就走到头了 //而若带环因为有速度差所以fast最终一定能找slow ListNode* fast head; ListNode* slow head; while(fast fast-next) { fast fast-next-next; slow slow-next; if(fast slow) { return true; } } return false;
}
2、深拷贝
typedef struct Node Node;
struct Node* copyRandomList(struct Node* head) { //第一步将用于复制的节点都插在对应节点的后面 Node* cur head; while(cur) { Node* copy (Node*)malloc(sizeof(Node)); copy-val cur-val; copy-next copy-random NULL; copy-next cur-next; cur-next copy; cur copy-next; } //第二步处理copy节点的random指针 cur head; while(cur) { Node* copy cur-next; if(cur-random NULL) { copy-random NULL; } else { copy-random cur-random-next; } cur copy-next; } //恢复原链表以及返回新链表 cur head; Node* newhead, *newtail; newhead newtail NULL; while(cur) { Node* copy cur-next; Node* next copy-next; if(newhead NULL) { newhead newtail copy; } else { newtail-next copy; newtail newtail-next; } cur-next next; cur next; } return newhead;
}
