Как я впервые столкнулся со связанными списками и не сдался

Всем привет!

Недавно я решил начать решать задачки на LeetCode. К этому я пришел, чтобы в будущем на собеседованиях не ударить в грязь лицом и уверенно справляться хотя бы с базовыми задачами на сортировку, работу со строками и тому подобное.

Сначала все шло неплохо: я успешно решал легкие задачки, используя обычные циклы (for, while). Редко когда надо было прям зависать и задумываться над решениями. Чаще, если даже решение было неверным, можно было в процессе искать ошибки и исправлять их. Но тут я наткнулся на задачу с пометкой "Easy" и названием "Merge Two Sorted Lists".

Прочитав название, я не обратил внимания на слово List и подумал, что это очередное задание на сортировку/конкатенацию массивов и в принципе обрадовался: “Щас решу в одну строку”, - подумал я. Однако компилятор остудил мой пыл.

Тогда я понял, что задача не так проста, как казалась и начал подробнее узнавать что же такое связанный список.

Что же такое связанный список?

Связанный список или же Linked List - это структура данных, в которой каждый элемент (узел) хранит два значения: данные и указатель-ссылку на следующий узел. Вот как примерно он выглядит на схеме:

Каждый узел в объекте содержит два параметра val и next. val возвращает данные хранящиеся в этом узле, а next содержит указатель-ссылку на следующий узел. Последний узел всегда указывает на null. На схеме я сделал третий узел ниже остальных, чтобы показать что объект LinkedList не располагается линейно в памяти, а разбросан по ней, и доступ к последующим элементам открывается только лишь по указателям.

Разбираемся с задачей

И так, поняв что же это такое пришло время снова перечитать условие задачи:

Вам даны заголовки двух отсортированных связанных списков list1 и list2.Объедините два списка в один отсортированный список. Список должен быть создан путем сращивания узлов первых двух списков. Верните заголовок объединенного связанного списка.

В задаче сказано вернуть “заголовок” связанного списка. Но что же это такое?

Заголовок (head) - это первый узел связанного списка, с которого начинается доступ ко всем остальным. Через него можно пройтись по всей цепочке узлов.

Сначала для работы с Связанным Списком нам понадобится написать функцию-конструктор которая содержит два параметра val, next. Этот код находился прямо в комментариях к задаче. По умолчанию val = 0, next = null. Что логично когда у нас пустой список у нас не может быть значения, так же как и указателя на следующий узел.

  function ListNode(val, next) {
    this.val = (val===undefined ? 0 : val)
    this.next = (next===undefined ? null : next)
  }

Далее мы создаём два связанных списка. (Если вы пишете решение прямо на LeetCode, создавать их вручную не нужно — как и конструктор ListNode, он уже задан системой. Но я предпочитаю сначала писать и тестировать код в Visual Studio Code, поэтому добавил эти части вручную.)

let list1 = new ListNode(1, new ListNode(2, new ListNode(4)))
let list2 = new ListNode(1, new ListNode(3, new ListNode(4)))

Как можно увидеть тут есть вложенные вызовы, то есть начинаем с первого значения (тут это 1) и вторым параметром передаем новый узел, который в себе содержит значение и ссылку на следующий новый узел и так далее. Таким способом мы получаем два связанных списка:

list1: 1→2→4

list2: 1→3→4

В результате мы должны получить один новый связанный список:

output: 1→1→2→3→4→4

Понимая, как устроены связанные списки, можем приступить к решению

Алгоритм:

1. создаем пустой узел - dummy, который будеv использовать как начало/заголовок.

2. создаем переменную current, которая будет "прицелом" и указывать, куда добавлять следующий элемент.

3. создаем цикл который будет работать пока один из списков не закончится т.е не станет null. while(list1 && list2) .

4. в каждой итерации будет сравнивать текущий элемент первого узла с текущим элементом второго.

5. если элемент первого/второго списка окажется меньше мы записываем всю цепочку в наш “прицел” и смещаем первый/второй список на один вперед.

6. после каждого сравнения смещаем “прицел” на один вперед.

7. возвращаем dummy.next, т.е. реальное начало нового списка (первый узел после фиктивного).

Вот как это будет выглядеть на практике:

const mergeTwoLists = function(list1,list2){
  let dummy = new ListNode() // новый пустой узел 
  let current = dummy // указатель на пустой узел
  while(list1 && list2){ // цикл выполняется пока не закончится один из списков
    if(list1.val < list2.val){ // проверка каждого элемента в списке
      current.next = list1 // записываем во второй элемент вcю цепочку узлов list1 
      list1 = list1.next // смещаем узел list1 на один элемент правее.
    } else {
      current.next = list2
      list2 = list2.next
    }
    current = current.next // после каждого сравнения не забываем передвинуть указатель
  }
  current.next = list1 || list2 // добавляем то что осталось от второго списка
  return dummy.next // возвращаем наш исходный пустой узел в который сохранялись значения кроме первого значения 
}

Как мы видим скорость не самая высокая, но решение вполне понятно и работает.)

Заключение

Решив эту задачу я понял сразу две вещи:

1. Не все задачи с пометкой "easy" легко решить за несколько минут - иногда это вопрос знаний, а не сложности.

2. Понять структуру - 70% пути к решению

После того как задача наконец решилась, я почувствовал радость и настоящее ощущение прогресса. Именно такие моменты и питают стремление двигаться дальше, учиться новому и не сдаваться. Я рад, что LeetCode помогает мне — как и тысячам других людей — развиваться в программировании, шаг за шагом приближаясь к новым вершинам и целям.