通俗点聊聊算法 -- 链表误成环
为什么链表会误成环
来看一个栗子,最近刷题刷链表,经常一不小心就下弄成环然后死循环了。
//ListNode* reverseList(ListNode* head)
//{
// ListNode* node_temp;
// ListNode* new_head;
//
// node_temp = head;
// //遍历一个节点,就把它拿下来放到头去
// while (head->next != NULL)
// {
// //先考虑只又两个节点的情况
// head = head->next;
// new_head = head;
// new_head->next = node_temp;
// node_temp = new_head;
// }
// return new_head;
//}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
像这样的,用原有节点进行赋值,就容易成环。
因为当我把一个原有节点直接挂载到另外一个节点之下时,其实是将其后续节点一并带过去了。
正确的做法应该是新建一个节点,然后将需要挂载的节点的内容拷贝到新节点里面,使用新节点去挂载。
如果对链表操作不熟,建议先了解一下:回顾通用链表 - 亲测代码示例
当然,我的好兄弟以为他很了解链表,反正他这两天一直绕在环里面出不来。
如何判断链表有环
喔,把你的环,我的环,串一串,串成一个同心圆,出不去,死循环。
其实说简单也简单,快慢指针就解决了,快指针两步走,慢指针一步走,只要两个指针重合了,那就说明有环,因为快指针绕回来了。
时间复杂度为线性,空间复杂度为常数。
说不简单也不简单,因为你去判断一个链表是否有环,那顶多是在测试环节,放在发布环节未免显得太刻意,连代码是否安全都不能保证。
而且,有环的话一般是运行不过的,不用测,运行超时妥妥要考虑一下环的情况,一调试就知道了。
如何判断环的大小
有了上面的基础,其实判断大小是很简单的。当快慢指针相遇的时候,别停,继续走,并开始计数,当再次相遇的时候,慢指针走了多少位置,那就是环的长度。
判断环的入口
这个就比较有意思了,这个不画图可能听不明白。
我这个人,懒了点,来张现成的图吧。
看啊,在相遇之前呢,慢指针走的距离很好求的:L1 = D+S1;
快指针走的距离:设它在相遇前绕了n圈(n>1),那么:L2 = D+S1+n(S1+S2);
不过,还有一个等量关系,不要忽略掉,快指针的速度是慢指针的两倍,所以:L2 = 2L1;
那么就是:n(S1+S2)-S1 = D;
再转换一下就是:(n-1)(S1+S2)+S2 = D;
那也就是说,在相遇时候,把一个慢指针放在链表头,开始遍历,把一个慢指针放在相遇点开始转圈,当它俩相遇的时候,就是入环点了。
其实吧,用脑子想一开始很难想出来,用手想就快多了。
文章来源: lion-wu.blog.csdn.net,作者:看,未来,版权归原作者所有,如需转载,请联系作者。
原文链接:lion-wu.blog.csdn.net/article/details/105861223
- 点赞
- 收藏
- 关注作者
评论(0)