个人随笔
目录
用快慢双指针法解决链表是否有环判定问题
2022-05-18 23:11:41

我们都直到,双指针法非常好用,比如做合并两个有序数组或者链表等算法,下面介绍一种双指针的新用法,就是判断链表是否有环,对应的其实是leetcode141题,题目描述如下:

题目

给你一个链表的头节点 head ,判断链表中是否有环。如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。

Hash法

其实最简单想得到的就是用一个hash存储节点,遍历链表,如果当前节点在hash表中,表明已经遍历过了,也就表明有环,如果不存在则放入hash表中。

但是这种解法空间复杂度也是O(n)

其实题目还有一个进阶:你能用 O(1)(即,常量)内存解决此问题吗?那么我们就用快慢双指针法来解决

快慢双指针法

我们知道,如果链表有环,我们定义两个指针从同一个节点开始出发,指针1一下子走两步,指针2一下子走1步,如果链表有环,因为指针1走的比较快,那么指针1最后肯定会绕一个圈追上指针1.

我们上面指的一下子走两步的指针1就是快慢双指针中的快指针,而走一步的指针2就是慢指针,根据上面的分析,发现这种方法是可行的,并且空间复杂度也满足O(1).代码也很好实现,如下

  1. /**
  2. * Definition for singly-linked list.
  3. * class ListNode {
  4. * int val;
  5. * ListNode next;
  6. * ListNode(int x) {
  7. * val = x;
  8. * next = null;
  9. * }
  10. * }
  11. */
  12. public class Solution {
  13. public boolean hasCycle(ListNode head) {
  14. if(head==null){
  15. return false;
  16. }
  17. //定义一个快指针
  18. ListNode fast = head;
  19. ListNode slow = head;
  20. while(fast.next!=null&&fast.next.next!=null){
  21. fast = fast.next.next;
  22. slow = slow.next;
  23. if(fast==slow){
  24. return true;
  25. }
  26. }
  27. return false;
  28. }
  29. }
 118

啊!这个可能是世界上最丑的留言输入框功能~


当然,也是最丑的留言列表

有疑问发邮件到 : suibibk@qq.com 侵权立删
Copyright : 个人随笔   备案号 : 粤ICP备18099399号-2