## sometimes, there is no clever and informative post title pun

There comes a time in every programmer’s life where they must consume Cracking the Coding Interview. That time has come for me, and now I’m all wrapped up in data structures and algorithms.

Today, I’ll show you some things I’ve done with Singly Linked Lists.

First, I made some. It turns out you won’t always need a LinkedList class that stores the entire list — if you can reference the bottom node, it’ll know about the node above it (which in turn will know about the node above it). (Eventually, we’ll use the self.list attribute from the initializer to store more info, but we don’t need it.)

`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`

Then, because I’d heard this was a common interview question, I decided to write up a way to reverse them. I really dig recursion when it behaves itself.

`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 endend`

Then, I decided I wanted to see if I could use recursion to make a linked list out of an array. Answer? Yes I can!

`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) endend`

Finally, I decided to actually tackle one of the problems in the book. The problem was as follows:

You have two numbers represented by a linked list, where each node contains a single digit. The digit are stored in reverse order, such that the 1’s digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.
`(7->1->6) + (5->9->2) => (9->1->2)617 + 295 = 912 `

First, I made the two lists we need to make the problem.

`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)`

At last, it was time to use my self.list attribute to store the entire list as an array.

`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]`

Once I had that method, I could reverse those arrays, then turn them into numbers.

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

So to sum both lists:

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

But finally, I have to turn that integer back into a linked list! Luckily, I made that “generate” method earlier. I did make that for arrays, so I’ll need to coerce the data a few times to make it work here.

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

Phew! I’m sure there is some refactoring I could be doing, but for now, I’ll leave you with a gist of all that code.

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.