描述
判断给定的链表中是否有环。如果有环则返回true,否则返回false。
你能给出空间复杂度的解法么?
输入分为2部分,第一部分为链表,第二部分代表是否有环,然后回组成head头结点传入到函数里面。-1代表无环,其他的数字代表有环,这些参数解释仅仅是为了方便读者自测调试
示例1:
输入:{3,2,0,-4},1 返回值:true 说明: 第一部分{3,2,0,-4}代表一个链表,第二部分的1表示,-4到位置1,即-4->2存在一个链接,组成传入的head为一个带环的链表 ,返回true
示例2:
输入:{1},-1 返回值:false 说明: 第一部分{1}代表一个链表,-1代表无环,组成传入head为一个无环的单链表,返回false
示例:
输入:{-1,-7,7,-4,19,6,-9,-5,-2,-5},6 返回值:true
思路
如上图就是一个环形链表,他是有一个闭环的,他有一个特性:那就是如果顺着链表一直往前走,永远也走不到头。
这个特性一会证明链表是否有环的时候会用到。
咱们想想这么一个场景:在操场跑圈的时候,一个跑的快的人如果跑的时间够长最后会超过跑的慢的人。为啥那,因为操场是一个环形,没有尽头。所以如果一个链表如果是环形的,那么咱们可以找两个“运动员”去链表上跑一跑,也就是快慢指针,不就可以了。
public boolean hasCycle(ListNode head) { if (head == null) { return false; } // 慢指针 ListNode slow = head; // 快指针 ListNode fast = head.next; // 如果fast == null 或 fast.next == null,说明有终点,就不是环形 while (fast != null && fast.next != null) { // 当快慢指针相遇,说明快的追上了慢的,链表有环!!! if (slow == fast) { return true; } // 慢指针移动 slow = slow.next; // 快指针移动 fast = fast.next.next; } return false; }
时间复杂度:O(n),n 为链表长度
空间复杂度:O(1)
最后
这道题主要运用快慢指针的方式来解决的,其实很多题都是源于生活,只要咱们善于观察,相信自己也可以编写一道这样的经典题!
大家可以去 【牛客网-题库-在线编程】去练习一下。
可以去微信搜索:【蘑菇睡不着】交个朋友~
也可以扫描下方二维码。