LeetCode.141.Linked List Cycle 判断链表是否有环

题目描述

141 Linked List Cycle https://leetcode-cn.com/problems/linked-list-cycle/ https://leetcode.com/problems/linked-list-cycle/description/

Given a linked list, determine if it has a cycle in it.

Follow up: Can you solve it without using extra space?

相似题目

Floyd判圈算法/龟兔赛跑算法

有环单链表的环长、环起点和链表长 LeetCode.141.Linked List Cycle 判断链表是否有环 LeetCode.142.Linked List Cycle II 有环链表的环起点

判圈算法的其他应用 LeetCode.287.Find the Duplicate Number 数组中重复的数 LeetCode.202.Happy Number 快乐数

解题过程

有环单链表的环长、环起点和链表长

这道题三年前准备校招面试的时候做过，面试过程中也被问到过不止一次，印象很深刻，知道是用双指针做，但具体怎么做有点儿模糊了。昨晚睡前看了这道题后躺床上就想，由于知道用双指针，思维被固话了，使劲想怎么往双指针上靠，不一会儿想出来了：一快一慢两个指针，快的步长为2，慢的步长为1，如果两个指针重合了就说明有环。

说实话，如果从来没做过这道题，从头开始想，可能根本不知道怎么做，但永远不会有这种机会了，这道题想忘都忘不了。

代码写起来也很简单，注意快指针往前走时要判断next是否为null，否则会报空指针错误，一次AC：

class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(slow!=null && fast!=null){
            slow = slow.next;
            if(fast.next !=null)
                fast = fast.next.next;
            else
                return false;
            if(slow==fast)
                return true;
        }
        return false;
    }
}

public class LinkedListCycle {
    public static void main(String[] args){
        ListNode head = new ListNode(1);
        ListNode second = new ListNode(2);
        ListNode third = new ListNode(3);
        head.next = head;
        second.next = third;
        third.next = head;
        Solution solution = new Solution();
        System.out.println(solution.hasCycle(head));
    }
}

在讨论区看到两个比较奇葩的方法，一个是把遍历过的结点值都设为Integer.MIN_VALUE，虽然笨但也可行：

public class Solution {
    public boolean hasCycle(ListNode head) {
        while(head != null && head.next != null) {
            if(head.val == Integer.MIN_VALUE)
                return true;
            head.val = Integer.MIN_VALUE;
            head = head.next;
        }
        return false;
    }
}

还有一个是用递归，把遍历过的结点的next指针都指向head，如果某次遇到指向head的结点则说明有环：

class HasCycleInLinkedList{
  public boolean hasCycle(ListNode head){
      if(head == null || head.next == null) return false;
      if(head.next == head) return true;
      ListNode nextNode = head.next;
      head.next = head;
      boolean isCycle = hasCycle(nextNode);
      return isCycle;
  }
}

不过这两种方法都会修改链表结构，如果题目再加一个不允许修改链表的条件就不能用了。

GitHub代码

algorithms/leetcode/leetcode/_141_LinkedListCycle.java https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_141_LinkedListCycle.java