Linked list

Create list

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

let addNode = (node, nodeToAdd) => {
  let prevNode = node.prev;
  nodeToAdd.next = node;
  nodeToAdd.prev = prevNode;
  prevNode.next = nodeToAdd;
  node.prev = nodeToAdd;
};

let deleteNode = (node) => {
  let prevNode = node.prev;
  let nextNode = node.next;
  prevNode.next = nextNode;
  nextNode.prev = prevNode;
};

Fast and slow pointer

let fn = (head) => {
  let slow = head;
  let fast = head;
  let ans = 0;

  while (fast && fast.next) {
    // do logic
    slow = slow.next;
    fast = fast.next.next;
  }

  return ans;
};

Reverse

let fn = (head) => {
  let curr = head;
  let prev = null;
  while (curr) {
    let nextNode = curr.next;
    curr.next = prev;
    prev = curr;
    curr = nextNode;
  }

  return prev;
};

Delete duplicates

Remove Duplicates from Sorted List

var deleteDuplicates = function (head) {
  let curr = head;

  while (curr && curr.next) {
    if (curr.val === curr.next.val) {
      curr.next = curr.next.next;
    } else {
      curr = curr.next;
    }
  }

  return head;
};

Remove from the end

For example, given the linked list that represents 1 -> 2 -> 3 -> 4 -> 5 and k = 2, return the node with value 4, as it is the 2nd node from the end.

let findNode = (head, k) => {
  let slow = head;
  let fast = head;
  for (let i = 0; i < k; i++) {
    fast = fast.next;
  }

  while (fast) {
    slow = slow.next;
    fast = fast.next;
  }

  return slow;
};

Examples

Reverse Linked List II

Input: head = [1,2,3,4,5], left = 2, right = 4 Output: [1,4,3,2,5]

var reverseBetween = function (head, left, right) {
  if (!head) return head;

  let dummy = new ListNode(0, head);
  let prevLeft = dummy;
  let leftVal = dummy;

  for (let i = 0; i < left; i++) {
    prevLeft = leftVal;
    leftVal = leftVal.next;
  }

  let prev = null;
  let curr = leftVal;
  let nextNode = curr.next;

  for (let i = left; i <= right; i++) {
    nextNode = curr.next;
    curr.next = prev;
    prev = curr;
    curr = nextNode;
  }

  prevLeft.next = prev;
  leftVal.next = curr;
  return dummy.next;
};

Palindrome Linked List

var isPalindrome = function (head) {
  if (!head.next) return true;

  let slow = head;
  let fast = head;

  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }

  let prev = null;
  let curr = slow;
  while (curr) {
    let nextNode = curr.next;
    curr.next = prev;
    prev = curr;
    curr = nextNode;
  }

  let first = head;
  let second = prev;
  while (second) {
    if (first.val !== second.val) {
      return false;
    }

    first = first.next;
    second = second.next;
  }

  return true;
};