leetCode 141 Linked List Cycle

• 关键字：链表、双指针
• 难度：easy
• 题目大意：检测给定的链表是否存在环

题目：

Given a linked list, determine if it has a cycle in it.
Can you solve it using *O(1)* (i.e. constant) memory?

解题思路：

1、采用双指针，起始双指针均指向头结点，fast指针每次走两步，slow指针每次走一步，如果有环，fast和slow最终会相遇。
2、（假设链表无重复节点）也可以采用map记录链表的每一个节点，如果包含重复节点，直接return true；否则，return false。

AC代码

/**
 * 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) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }
}

下面的代码也可以AC，严格来讲，如果链表节点的值有重复，这种解法是错误的（ 看了solution，题目貌似默认链表无重复节点），例如：Testcase：input：[2,2,2,-4] -1

/**
 * 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) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null&&fast.next!=null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast!=null&&slow!=null) {
                if(fast.val==slow.val) {  //节点值相等时，该方法错误
                    return true;
                }
            }
        }
        return false;
    }
}