Fast/Slow Pointers: Linked List Cycle

by Raul Bojalil

HTML

<div class="markdownViewer select-text  markdown-default markdown-table markdown-viewer markdown-viewer-heading" role="none"><h2 class="hover-anchor" id="Statement" data-id="e912159ba4656d694eefa773cabf35b3">Statement<a href="#Statement"><span class="anchor-link">#</span></a></h2>
<p data-id="6484ba8fe2dd63b92f9569f15493f324">Check whether or not a linked list contains a cycle. If a cycle exists, return TRUE. Otherwise, return FALSE. The cycle means that at least one node can be reached again by traversing the <code>next</code> pointer.</p>
<p data-id="ca20951bb707c77e4acb170f3e61b689"><strong>Constraints:</strong></p>
<p data-id="4cd4602163fac7593d3bd69282612423">Let <code>n</code> be the number of nodes in a linked list.</p>
<ul data-id="d2bb0ef14e6d17d3bc1810b0e018a8f6">
<li><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>0</mn><mo>≤</mo></mrow><annotation encoding="application/x-tex">0\leq</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7804em;vertical-align:-0.136em;"></span><span class="mord">0</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">≤</span></span></span></span> <code>n</code> <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo>≤</mo><mn>500</mn></mrow><annotation encoding="application/x-tex">\leq500</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7719em;vertical-align:-0.136em;"></span><span class="mrel">≤</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">500</span></span></span></span></li>
<li><span class="katex"><span class="katex-mathml"><math...

JavaScript

class LinkedListNode {
    constructor(data, next = null) {
        this.data = data;
        this.next = next;
    }
}

// Template for the linked list
class LinkedList {
    constructor() {
        this.head = null;

        // insertNodeAtHead method will insert a LinkedListNode at head
        // of a linked list.
        this.insertNodeAtHead = function (node) {
            if (this.head != null) {
                node.next = this.head;
                this.head = node;
            } else this.head = node;
        };

        // createLinkedList method will create the linked list using the
        // given integer array with the help of InsertAthead method.
        this.createLinkedList = function (list) {
            list.reverse().forEach((element) => {
                let newNode = new LinkedListNode(element);
                this.insertNodeAtHead(newNode);
            });
        };
        // returns the number of nodes in the linked list
        this.getLength = function (head) {
            let length = 0,
                temp = head;
            while (temp != null) {
                length++;
                temp = temp.next;
            }
            return length;
        }
        // returns the node at the specified position(index) of the linked list
        this.getNode = function (head, pos) {
            if (pos !== -1) {
                let p = 0;
                let ptr = head;
                while (p < pos) {
                ptr = ptr.next;
                p += 1;
                }
                return ptr;
            }
        }

        // This method will display the elements of the linked list.
        this.display = function () {
            let result = "",
                temp = this.head;
            while (temp != null) {
                result += temp.data;
                temp = temp.next;
                if (temp != null) {
                    result += ", ";
                }
            }
            result += "";
       ...