每天一道leetcode141-环形链表

乔戈里

发布于 2019-09-17 15:11:15

2480

发布于 2019-09-17 15:11:15

文章被收录于专栏：Java那些事

题目

每天一道leetcode141-环形链表分类：链表中文链接： https://leetcode-cn.com/problems/linked-list-cycle/description/ 英文链接 https://leetcode.com/problems/linked-list-cycle/description/

题目详述

给定一个链表，判断链表中是否有环。进阶：你能否不使用额外空间解决此题？

题目详解

思路

使用两个指针，一个快指针，一个慢指针；
快的每次走两步，慢的每次走一步，如果有环，那么快的肯定可以追上慢点，两者相等

代码

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null)
            return false;
        ListNode fast = head.next;
        ListNode slow = head;
        while(slow != null && fast != null)
        {
            if(fast == slow)
                return true;
            slow = slow.next;
            if(fast.next != null)
                fast = fast.next.next;
            else
                return false;
        }
        return false;
    }
}