JS - Two-Pointer Linked List Techniques

Qns: Create a function that returns the nth last element of a singly linked list.

Approach 1: Creating an entire parallel list

Use an array to store a representation of the linked list.

Use up lots of memory maintaining a dual representation of the same data
An approach like this results in an extra O(n) space being allocated.

const arrayNthLast = (list, n) => {
  const linkedListArray = [];
  let currentNode = list.removeHead();
  while (currentNode) {
    linkedListArray.push(currentNode);
    currentNode = currentNode.getNextNode();
  }
  return linkedListArray[linkedListArray.length - n];
};

Approach 2: Two-pointers

O(n) time (we must iterate through the entire list once).
O(1) space complexity (we always use only three variables no matter what size the list is).

const LinkedList = require('./LinkedList');
const testLinkedList = require('./testLinkedList.js');
 
const nthLastNode = (linkedList, n) => {
  let current = null;
  let tailSeeker = linkedList.head;
  let count = 0;
  while (tailSeeker) {
    tailSeeker = tailSeeker.next;
    if (count >= n) {
      if (!current) {
        current = linkedList.head;
      }
      current = current.next;
    }
    count++;
  }
  return current;
};
 
console.log(nthLastNode(testLinkedList, 4));

Qns: Find the middle node of a linked list.

Approach: Two-pointers at Different Speeds

Return the right-weighted middle for even-length lists.
For example, in a list of 4 elements, return the element at index 2 (which would be the element 3).

Different speeds pointers

const generateTestLinkedList = require('./generateTestLinkedList');
 
const findMiddle = (linkedList) => {
  let fast = linkedList.head;
  let slow = linkedList.head;
 
  // As long as the end of the list is not reached
  while (fast !== null) {
    // Move the fast pointer at least one step
    fast = fast.getNextNode();
    // If it isn't at the end of the list
    if (fast !== null) {
      // Move both pointers forward once
      fast = fast.getNextNode();
      slow = slow.getNextNode();
    }
  }
  // At this point, the slow pointer is in the middle
  return slow;
};
 
// Test your function yourself:
console.log(findMiddle(generateTestLinkedList(7)));
 
// Leave this so that we can test your code:
module.exports = findMiddle;

Half-Speed

Another equally valid solution is to move the fast pointer once with each loop iteration,
but only move the slow pointer every-other iteration.

Alternative

const findMiddleAlternate = (linkedList) => {
  let count = 0;
  let fast = linkedList.head;
  let slow = linkedList.head;
 
  while (fast !== null) {
    fast = fast.getNextNode();
    if (count % 2 !== 0) {
      slow = slow.getNextNode();
    }
    count++;
  }
  return slow;
};