Объединение односвязных списков в JavaScript

Связанные списки — это важная для понимания структура данных. Хотя они не так популярны, как массивы, в некоторых случаях они более эффективны. В этом блоге я расскажу об основах связанных списков и обсужу, как объединить отсортированный связанный список.

Создание односвязного списка

Логика односвязных списков относительно проста: у вас есть набор узлов, и каждый узел указывает на следующий узел в последовательности. Однако реализация связанного списка в коде может быть немного сложной, в первую очередь из-за синтаксиса и концепций, которые вам необходимо усвоить. Один из часто используемых подходов к созданию связанного списка — определение конструктора.

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

После создания конструктора мы можем создать связанный список следующим образом.

// create and connect nodes
const node1 = new ListNode(1)
node1.next = new ListNode(2)
node1.next.next = new ListNode(3)
console.log(node1) 
/* output: -> ListNode {
  val: 1,
  next: ListNode { val: 2, next: ListNode { val: 3, next: null } }
} */

Как только список создан, мы можем перебирать его следующим образом.

let current = node1
while(current) {
  console.log(current.val)
  current = current.next
}
// output: 1 -> 2 -> 3

Объединение двух отсортированных списков

Теперь, когда мы понимаем основы связанного списка, мы можем объединить отсортированный список. Здесь у нас есть два списка: список 1 и список 2:

function ListNode(val, next) {
  this.val = val
  this.next = next || null
}

const list1 = new ListNode(1);
list1.next =  new ListNode(2);
list1.next.next =  new ListNode(3);

console.log(list1)
/* output: -> ListNode {
  val: 1,
  next: ListNode { val: 2, next: ListNode { val: 3, next: null } }
} */

const list2 = new ListNode(1);
list2.next = new ListNode(1);
list2.next.next = new ListNode(4);

console.log(list2)
/* output: -> ListNode {
  val: 1,
  next: ListNode { val: 1, next: ListNode { val: 4, next: null } }
}*/

Теперь, когда у нас есть оба списка, мы можем создать функцию слияния.

function mergeSortedLists(list1, list2) {
  // Initialize a dummy node as the head of the merged list
  const dummyNode = new ListNode(0);
  // Set a pointer to the current node, initially pointing to the dummy node
  let current = dummyNode;

  // Iterate through both lists while both contain elements
  while (list1 !== null && list2 !== null) {
    // Compare the values of the current nodes
    if (list1.val < list2.val) {
      // Set the current.next to the smaller list1 value
      current.next = list1;
      // Move the list1 pointer to the next node
      list1 = list1.next;
    } else {
      // Set the current.next to the smaller list2 value
      current.next = list2;
      // Move the list2 pointer to the next node
      list2 = list2.next;
    }
    // Move 'current' to the newly added node
    current = current.next;
  }

  // After the loop, one of the lists might still have remaining elements
  // Check which list has remaining elements and append them to the merged list
  if (list1 !== null) {
    current.next = list1;
  } else {
    current.next = list2;
  }

  // The merged list starts from the node after the dummy node
  return dummyNode.next;
}

Короче говоря, эта функция создает фиктивный узел в качестве отправной точки объединенного списка. Затем он эффективно объединяет два отсортированных связанных списка, проходя по обоим спискам и добавляя меньшее значение к этому фиктивному узлу. Кроме того, он проверяет, остались ли элементы list1 или list2 после основного цикла слияния, и добавляет все оставшиеся элементы в объединенный список перед возвратом окончательного списка.

В заключение я хочу признать, что недавно углубился в мир связанных списков в JavaScript. Изучение этих концепций было одновременно трудным и полезным. Продолжая исследовать тонкости структур данных и алгоритмов, я надеюсь, что этот пост в блоге послужит полезным ресурсом для тех, кто также находится на пути непрерывного обучения.