Two Pointers: Remove nth Node from End of List

by Raul Bojalil

HTML

<p data-id="20f90fa30042a58dfee04a061b36b34c">Given a singly linked list, remove the <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msup><mi>n</mi><mrow><mi>t</mi><mi>h</mi></mrow></msup></mrow><annotation encoding="application/x-tex">n^{th}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8491em;"></span><span class="mord"><span class="mord mathnormal">n</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8491em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathnormal mtight">t</span><span class="mord mathnormal mtight">h</span></span></span></span></span></span></span></span></span></span></span></span> node from the end of the list and return its head.</p>

<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>
<ol data-id="5a28c7191a2cda0d029e0762e1efde29">
<li>Two pointers, <code>right</code> and <code>left</code>, are set at the head node.</li>
<li>Move the <code>right</code> pointer <code>n</code> steps forward.</li>
<li>If <code>right</code> reaches NULL, return <code>head</code>'s next node.</li>
<li>Move both <code>right</code> and <code>left</code> pointers forward till <code>right</code> reaches the last node.</li>
<li>Relink the <code>left</code> node to the node at <code>left</code>'s next to the next node.</li>
<li>Return <code>head</code>.</li>
</ol>
<h4 class="hover-anchor" id="Time-complexity" data-id="e7551b98ca1180b803b88ad14ecc30ed">Time complexity<a...

JavaScript

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

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

function removeNthLastNode(head, n) {

	let rp = head;
  let lp = head;
  
  for (let i=0; i < n; i++) {
  	rp = rp.next;
  }
  
  if (!rp) {
  	return lp.next;
  }
  
  while(rp.next != null) {
     rp = rp.next;
     lp = lp.next;
  }
  
  lp.next = lp.next.next;
  
  return head;
}

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

const inputs = [
  [23, 89, 10,...