判断链表中是否有环

给定一个链表结构，判断链表中是否存在环。

class ListNode {
     int val;
     ListNode next;
     ListNode(int x) {
         val = x;
         next = null;
     }
 }

解法一：set方法

最容易相当的一种方法就是用集合类，来判断遍历的过程中是否存在重复的节点。这种方法的时间复杂度和空间复杂度都是

O

(

n

)

O(n)

O(n)

import java.util.*;
public class Solution {
    public boolean hasCycle(ListNode head) {
        HashSet<ListNode> set = new HashSet<>();
        ListNode ptr = head;
        while(ptr!=null){
            if(!set.add(ptr)){
                return true;
            }
            ptr = ptr.next;
        }
        return false;
    }
}

在 LeetCode 系统中提交的结果为

执行结果：通过 显示详情
执行用时：4 ms, 在所有 Java 提交中击败了21.87%的用户
内存消耗：39 MB, 在所有 Java 提交中击败了44.18%的用户

解法二：将所有的节点的next都指向头节点

要能够意识到，这个问题，在时间复杂度上，不可能存在最坏时间复杂度优于

O

(

n

)

O(n)

O(n)的方法。但是空间复杂度还有优化的余地。我们可以把遍历过的节点的next值修改为指向头结点，或我们自己定义的一个节点。如果后面新遍历到的节点的next值指向该节点，说明原链表中存在环。这样可以将空间复杂度降低到

O

(

1

)

O(1)

O(1)，但是这个方法的缺点是破坏了原来的链表结构。下面是具体的代码实现。

public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null){
            return false;
        }

        ListNode last = head;
        ListNode current = head.next;
        while(current!=null){
            if(head==current.next){
                return true;
            }
            last = current;
            current = current.next;
            last.next = head;
        }
        return false;
    }
}

在 LeetCode 系统中提交的结果为

执行结果：通过 显示详情
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：38.8 MB, 在所有 Java 提交中击败了68.73%的用户

由于只涉及简单的指针操作，而没有复杂的集合。所以时间要比用集合的方法快很多，但是这种方法破坏了原来的链表结构。

解法三：快慢指针

可以用一快一慢两个指针，来解决这个问题。两个指针初始都指向头结点，快指针每次走两步，慢指针每次走一步。如果两个指针能够遇上，则一定存在环。这个证明比较简单，就先略过了。下面是具体的代码实现。这种方法的时间复杂度为

O

(

n

)

O(n)

O(n)，空间复杂度为

O

(

1

)

O(1)

O(1)。

public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null){
            return false;
        }

        ListNode fast = head;
        ListNode slow = head;

        while(fast.next!=null && fast.next.next!=null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast==slow){
                return true;
            }
        }
        return false;
    }
}

在LeetCode系统中提交的结果为

执行结果：通过显示详情
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：38.8 MB, 在所有 Java 提交中击败了77.33%的用户