иногда нет умной и информативной каламбура в заголовке поста

В жизни каждого программиста наступает момент, когда он должен пройти Cracking the Coding Interview. Это время для меня настало, и теперь я полностью поглощен структурами данных и алгоритмами.

Сегодня я покажу вам кое-что, что я сделал с помощью односвязных списков.

Сначала я приготовил. Оказывается, вам не всегда нужен класс LinkedList, в котором хранится весь список - если вы можете сослаться на нижний узел, он будет знать об узле над ним (который, в свою очередь, будет знать об узле над ним). (В конце концов, мы будем использовать атрибут self.list из инициализатора для хранения дополнительной информации, но нам это не нужно.)

class LinkedListNode
 attr_accessor :value, :next_node, :list
 def initialize(value, next_node=nil)
  @value = value
  @list = []
  @next_node = next_node
 end
 def print
  p @value
  if @next_node
   @next_node.print
  end
 end
end

Затем, поскольку я слышал, что это частый вопрос на собеседовании, я решил придумать способ их изменить. Я действительно копаю рекурсию, когда она себя ведет.

def reverse(bottom_node, previous=nil)
 head = bottom_node.next_node
 bottom_node.next_node = previous
 if head 
  reverse(head, bottom_node)
 else
  bottom_node
 end
end

Затем я решил, что хочу посмотреть, могу ли я использовать рекурсию для создания связного списка из массива. Отвечать? Да, я могу!

def generate(array, node=nil)
 if array.empty?
  node
 elsif node.nil?
  new_node = LinkedListNode.new(array.pop)
  generate(array, new_node)
 else 
  new_node = LinkedListNode.new(array.pop, node)
  generate(array, new_node)
 end
end

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

У вас есть два числа, представленных связанным списком, где каждый узел содержит одну цифру. Цифры сохраняются в обратном порядке, так что цифра 1 находится в начале списка. Напишите функцию, которая складывает два числа и возвращает сумму в виде связанного списка.

(7->1->6) + (5->9->2) => (9->1->2)
617 + 295 = 912

Во-первых, я составил два списка, которые нам нужны, чтобы решить проблему.

node1 = LinkedListNode.new(6)
node2 = LinkedListNode.new(1, node1)
list1 = LinkedListNode.new(7, node2)
node3 = LinkedListNode.new(2)
node4 = LinkedListNode.new(9, node3)
list2 = LinkedListNode.new(5, node4)

Наконец, пришло время использовать мой атрибут self.list для хранения всего списка в виде массива.

class LinkedListNode
…
 def numberify(node, array=@list)
  array.push(self.value)
  if @next_node
   @next_node.numberify(self, array)
  end 
 end
end
list1.numberify(list1)
p list1.list
=> [7, 1, 6]
list2.numberify(list2)
p list2.list
=> [5, 9, 2]

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

class LinkedListNode
…
def reverse_n_join
 self.list.reverse.join(‘’).to_i
end
end

Итак, чтобы суммировать оба списка:

def sum(lista, listb)
 lista.numberify(lista)
 listb.numberify(listb)
 return lista.reverse_n_join + listb.reverse_n_join
end
p sum(list1, list2)
=> 912

Но, наконец, мне нужно снова превратить это целое число в связанный список! К счастью, я сделал этот метод «генерации» раньше. Я сделал это для массивов, поэтому мне нужно несколько раз принудить данные, чтобы они работали здесь.

generate(sum(list1,list2).to_s.split(‘’).map(&:to_i)).print
=>9
=>1
=>2

Фух! Я уверен, что я мог бы провести некоторый рефакторинг, но пока я оставлю вам суть всего этого кода.