Algorithms Lesson 3: Linked Lists

A linked list is a chain of nodes where each node points to the next. No random access by index, but O(1) insertion at head. Linked list questions are interview staples.

Implementation

class Node {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

class LinkedList {
  constructor() { this.head = null; this.size = 0; }
  
  // Prepend: O(1)
  prepend(val) {
    const node = new Node(val);
    node.next = this.head;
    this.head = node;
    this.size++;
  }
  
  // Append: O(n) — must traverse to end
  append(val) {
    const node = new Node(val);
    if (!this.head) { this.head = node; this.size++; return; }
    let curr = this.head;
    while (curr.next) curr = curr.next;
    curr.next = node;
    this.size++;
  }
  
  // Delete: O(n)
  delete(val) {
    if (!this.head) return;
    if (this.head.val === val) { this.head = this.head.next; return; }
    let curr = this.head;
    while (curr.next && curr.next.val !== val) curr = curr.next;
    if (curr.next) curr.next = curr.next.next;
  }
  
  toArray() {
    const arr = [];
    let curr = this.head;
    while (curr) { arr.push(curr.val); curr = curr.next; }
    return arr;
  }
}

Classic Interview Problems

// Reverse a linked list (iterative)
function reverse(head) {
  let prev = null, curr = head;
  while (curr) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
}

// Detect cycle (Floyd's algorithm)
function hasCycle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}