Проход по списку

Запись в связный список

Обычно в задачах мы будем получать значение head. Но это просто обозначение некой переменной, которая может меняться в процессе прохождения по списку. В некоторых задачах, лучше не менять значение head.

let current = head;
current = current.next;
current = current.next;
current = null;

Путешествие по списку

Давайте предположим, что нам нужно сложить значения внутри связного списка. Пусть значение хранится в переменной val внутри нашего узла (node). Тогда все путешествие будет выглядеть вот так:

let getSum = (head) => {
  let ans = 0;
  while (head) {
    ans += head.val;
    head = head.next;
  }

  return ans;
};

Мы сделали простую итерацию вперед, которую нам предоставляет метод next. Но давайте не будем упускать важную вещь - в конце списка всегда есть null.

Поэтому мы можем обойтись 1 пойнтером и сделать сложение рекурсивно:

let getSum = (head) => {
  if (!head) {
    return 0;
  }

  return head.val + getSum(head.next);
};

Вставка в односвязный список по позиции

Допустим, вы хотите добавить элемент в связный список так, чтобы он стал элементом на позиции i. Для этого необходимо иметь указатель на элемент, который сейчас находится на позиции i - 1. Следующий элемент (текущий на позиции i), назовем его x, будет перемещен на позицию i + 1 после вставки.
Это значит, что x должен стать следующим узлом для добавляемого элемента, а добавляемый элемент должен стать следующим узлом для того, который находится на i - 1.

Вот пример кода и изображения, иллюстрирующие этот процесс

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

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

Добавим узел со значением 4 на позицию 2

Добавление sentinel nodes для контроля

Sentinel nodes находятся в начале и в конце связных списков и используются для упрощения операций и кода, необходимого для их выполнения. Идея заключается в том, что даже если в связном списке нет узлов, все равно остаются указатели на голову и хвост. Истинная голова списка — это head.next, а истинный хвост — это tail.prev. Сами Sentinel nodes не являются частью связного списка.

Ранее рассмотренный код подвержен ошибкам. Например, если мы попытаемся удалить последний узел в списке, то nextNode станет null, и попытка доступа к nextNode.next приведет к ошибке. С Sentinel nodes нам не нужно беспокоиться об этой ситуации, так как next последнего узла указывает на сторожевой узел хвоста.

Sentinel nodes также позволяют легко добавлять и удалять элементы в начале или в конце связного списка. Напомним, что добавление и удаление возможно за O(1), если у нас есть ссылка на узел, в котором выполняется операция. С помощью Sentinel nodes хвоста мы можем выполнять операции в конце списка за O(1).

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

let addToEnd = (nodeToAdd) => {
  nodeToAdd.next = tail;
  nodeToAdd.prev = tail.prev;
  tail.prev.next = nodeToAdd;
  tail.prev = nodeToAdd;
};

let removeFromEnd = () => {
  if (head.next == tail) {
    return;
  }

  let nodeToRemove = tail.prev;
  nodeToRemove.prev.next = tail;
  tail.prev = nodeToRemove.prev;
};

let addToStart = (nodeToAdd) => {
  nodeToAdd.prev = head;
  nodeToAdd.next = head.next;
  head.next.prev = nodeToAdd;
  head.next = nodeToAdd;
};

let removeFromStart = () => {
  if (head.next == tail) {
    return;
  }

  let nodeToRemove = head.next;
  nodeToRemove.next.prev = head;
  head.next = nodeToRemove.next;
};

let head = new ListNode(-1);
let tail = new ListNode(-1);
head.next = tail;
tail.prev = head;

Dummy pointers

Как упоминалось ранее, обычно мы хотим сохранить ссылку на голову списка, чтобы всегда иметь доступ к любому элементу. Иногда лучше использовать "временный" указатель (dummy pointer) для обхода списка, оставляя head на своем месте.

Использование временного указателя позволяет нам перемещаться по связному списку, не теряя ссылку на голову.

let getSum = (head) => {
  let ans = 0;
  let dummy = head;
  while (dummy) {
    ans += dummy.val;
    dummy = dummy.next;
  }
  return ans;
};