EXERCISE · AlgoCasts
From last (nth from end)
Given a linked list, return the element n spaces from the last node in the list. Do not call the 'size' method of the linked list.
Directions
Directions
Given a linked list, return the element n spaces from the last node in the list. Do not call the 'size' method of the linked list. Assume that n will always be less than the length of the list.
Examples#
JS
const list = new List(); list.insertLast('a'); list.insertLast('b'); list.insertLast('c'); list.insertLast('d'); fromLast(list, 2).data // 'b'Try it first#
Copy the stub, make the 2 tests pass on your machine, then open the solution. The reveal is remembered per page in this browser.
JSexercises/fromlast/index.js
function fromLast(list, n) {} module.exports = fromLast;Solution#
JScompleted_exercises/fromlast/index.js
function fromLast(list, n) { let slow = list.getFirst(); let fast = list.getFirst(); while (n > 0) { fast = fast.next; n--; } while (fast.next) { slow = slow.next; fast = fast.next; } return slow;} module.exports = fromLast;const fromLast = require('./index');const L = require('./linkedlist');const List = L.LinkedList;const Node = L.Node; test('fromLast is a function', () => { expect(typeof fromLast).toEqual('function');}); test('fromLast returns the node n elements from the end', () => { const l = new List(); l.insertLast('a'); l.insertLast('b'); l.insertLast('c'); l.insertLast('d'); l.insertLast('e'); expect(fromLast(l, 3).data).toEqual('b');}); class Node { constructor(data, next = null) { this.data = data; this.next = next; }} class LinkedList { constructor() { this.head = null; } insertFirst(data) { this.head = new Node(data, this.head); } size() { let counter = 0; let node = this.head; while (node) { counter++; node = node.next; } return counter; } getFirst() { return this.head; } getLast() { if (!this.head) { return null; } let node = this.head; while (node) { if (!node.next) { return node; } node = node.next; } } clear() { this.head = null; } removeFirst() { if (!this.head) { return; } this.head = this.head.next; } removeLast() { if (!this.head) { return; } if (!this.head.next) { this.head = null; return; } let previous = this.head; let node = this.head.next; while (node.next) { previous = node; node = node.next; } previous.next = null; } insertLast(data) { const last = this.getLast(); if (last) { // There are some existing nodes in our chain last.next = new Node(data); } else { // The chain is empty! this.head = new Node(data); } } getAt(index) { let counter = 0; let node = this.head; while (node) { if (counter === index) { return node; } counter++; node = node.next; } return null; } removeAt(index) { if (!this.head) { return; } if (index === 0) { this.head = this.head.next; return; } const previous = this.getAt(index - 1); if (!previous || !previous.next) { return; } previous.next = previous.next.next; } insertAt(data, index) { if (!this.head) { this.head = new Node(data); return; } if (index === 0) { this.head = new Node(data, this.head); return; } const previous = this.getAt(index - 1) || this.getLast(); const node = new Node(data, previous.next); previous.next = node; } forEach(fn) { let node = this.head; let counter = 0; while (node) { fn(node, counter); node = node.next; counter++; } } *[Symbol.iterator]() { let node = this.head; while (node) { yield node; node = node.next; } }} module.exports = { Node, LinkedList }; Verbatim from the repo at 30cf7634. Alternate tabs are the commented-out solutions with the leading // removed and nothing else changed. Run the tests locally with npx jest fromlast inside the fork.
See also