Fast/Slow Pointers: Middle of the Linked List

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="ff38c73dec04b778ef459696efda50b9">Given the <code>head</code> of a singly linked list, return the middle node of the linked list. If the number of nodes in the linked list is even, there will be two middle nodes, so return the second one.</p>
<p data-id="ca20951bb707c77e4acb170f3e61b689"><strong>Constraints:</strong></p>
<ul data-id="23dd2a545fd24094f5d634f8b5e444e3">
<li><code>head</code> <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo mathvariant="normal">≠</mo></mrow><annotation encoding="application/x-tex">\neq</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8889em;vertical-align:-0.1944em;"></span><span class="mrel"><span class="mrel"><span class="mord vbox"><span class="thinbox"><span class="rlap"><span class="strut" style="height:0.8889em;vertical-align:-0.1944em;"></span><span class="inner"><span class="mord"><span class="mrel"></span></span></span><span class="fix"></span></span></span></span></span><span class="mrel">=</span></span></span></span></span> NULL</li>
</ul>
</div>

<div class="markdownViewer select-text  markdown-default markdown-table markdown-viewer markdown-viewer-heading" role="none"><h4 class="hover-anchor" id="Solution-summary" data-id="87bbf7e35fe27305a7087e59419168c3">Solution summary<a href="#Solution-summary"><span class="anchor-link">#</span></a></h4>
<p data-id="8fdf3cd88b19e718ddf571e43f42155b">To recap, the solution to this problem can be divided into the following steps:</p>
<ol data-id="ad982090dd0f21c5b598413e06446090">
<li>Create two pointers, <code>slow</code> and...

JavaScript

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

function printListWithForwardArrow(linkedListNode) {
    let temp = linkedListNode;
    let result = "";
    while (temp != null) {
        result += temp.data;
        temp = temp.next;
        if (temp != null) result += " → ";
        // if this is the last node, print null at the end
        else result += " → null";
    }
    return result;
}


// 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);
            });
        };

        // 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 += "";
            return result;
        };
    }
}

// Function to find the middle node of the linked list
function getMiddleNode(head) {

  // Create two pointers, slow and fast ,initially pointing to the head
  let slow = head,
      fast = head;

  // Traverse the linked list until fast reaches at the last node or NULL
  while (fast...