LeetCode - 环形链表

题目链接

LeetCode 141. 环形链表

解题思路

主要思路是对于节点 val 修改数值，那么如果出现节点 next 存在，但是 val 不存在，那就是环形。然而这个明显不对的解，居然通过了。

代码实现

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    let current = new ListNode();
    current.next = head;
    
    while (current.next && current.val) {
        current.val = false;
        current = current.next;
    }
    
    if (current.next) {
        return true;
    }
    
    return false;
};

正确解法

使用双指针，也就是龟兔赛跑的想法，对于环形链表，总会追上。

if (head == null || head.next == null) {
    return false;
}

let slow = head;
let fast = head.next;

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

return true;