How to Reverse a Linked List in Ruby

How to reverse a linked list in Ruby

Here's a little visualization I made up.

^ points to head of the list. At each level of recursion, its right arrow is "turned" to point from element on the right to element on the left. Proceed until there is a right arrow (pointing to a non-nil). If right arrow points to nil, return the current head.

previous
↓
nil    12 -> 99 -> 37 -> nil
       ^

       previous
       ↓ 
nil <- 12       99 -> 37 -> nil
                ^

             previous
             ↓
nil <- 12 <- 99       37 -> nil
                      ^         

nil <- 12 <- 99 <- 37 
                   ^                            

How to reverse a LinkedList in place

In answer to your updated question:

Yes you will have to reverse the values of the list, instead of the pointers.

To do this AFAIK you have to first build a new reversed list, and then copy the reversed values back into the original list.

I have updated the original code to be more ruby-ish (i.e. the methods are part of the list class, and the "!" suffix is used to indicate the method will modify the object (rather than just return a new value.)

<script type="text/ruby">def print(s)  s = s.gsub("\n", "<br/>").gsub(" ", " ")  Element['#output'].html = Element['#output'].html + send
class LinkedListNode  attr_accessor :value, :next_node
  def initialize(value, next_node=nil)    @value = value    @next_node = next_node  end   def reverse_list(reversed=nil)    if next_node      next_node.reverse_list(LinkedListNode.new(value, reversed))    else      LinkedListNode.new(value, reversed)    end  end    def reverse_list!(list=self, reversed_list = reverse_list)    self.value = reversed_list.value    if next_node      next_node.reverse_list!(list, reversed_list.next_node)    else      list    end  end    def print_values    print "[#{object_id}]#{value} --> "    if next_node.nil?      print "nil\n"    else      next_node.print_values    end  end end
node1 = LinkedListNode.new(37)node2 = LinkedListNode.new(99, node1)node3 = LinkedListNode.new(12, node2)print "original list:     "node3.print_valuesprint "reversed list:     "node3.reverse_list.print_valuesprint "reversed in place: "node3.reverse_list!node3.print_values
</script>

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script><script src="https://rawgit.com/reactrb/reactrb-express/master/reactrb-express.js"></script><div id="output" style="font-family: courier"></div>

reversing a linked list in ruby using a stack

The following pushes the elements into the stack, and then reverses them:

def reverse_list(list) 
    stack = Stack.new

    while list
      stack.push(list.value)
      list = list.next_node
    end

  LinkedListNode.new(stack.pop, stack.data)
end

Reverse a LinkedList WITHOUT using array methods

You can use the Linked List datatype, rather than an array, to implement a Stack. I believe something like this would work:

def push(element)
  if data.nil?
    data = LinkedListNode.new(element, nil)
  else
    data = LinkedListNode.new(element, data)
  end
end

def pop
  # grab the top piece of data
  popped = data.value
  # shift the data
  data = data.next_node
end

Return head node of a linked list in Ruby?

Your problem is that you treat @head and previous_head as if they were different objects, but they are not.

When you call

previous_head.next = nil # I want to return a clean node, without nexts

the next attribute of previous_head (and consequently of @head) is set to nil, so when you try to access it again from @head it is already nil.

To solve this you need to reverse the order of operations, first setting the new @head and only then removing the next node from the previous_head:

  def return_head
    previous_head = @head
    @head = @head.next
    previous_head.next = nil # I want to return a clean node, without nexts
    return previous_head
  end

On a side note, you might also want to look at @Cary's answer, as your add_element method does not actually add an element, but rather replaces the second element (you'll have a list of zero, one or two element - no more...)

Why isn't my print_linked_list_in_reverse function working?

Your solution relies on return values, and you don't explicitly provide one in your else clause. In fact, you implicitly do because Ruby returns the result of the last statement evaluated, which for a print statement is nil. In Ruby false and nil are both logically false, causing the print to get bypassed for all but the last two calls. Your choices are to add a true at the end of the else, or make a solution that doesn't rely on return values.

To negate the need for return values, just check what logic is kosher based on info in the current invocation. You can simplify your life by leveraging the "truthiness" non-nil objects. Your basic recursive logic to get things in reverse is "print the stuff from the rest of my list, then print my stuff." A straightforward implementation based on truthiness would be:

def print_list_in_reverse(hash)
  print_list_in_reverse(hash[:next]) if hash[:next]
  print "#{hash[:data]}\n"
end

The problem with that is that you might have been handed an empty list, in which case you don't want to print anything. That's easy to check:

def print_list_in_reverse(hash)
  print_list_in_reverse(hash[:next]) if hash[:next]
  print "#{hash[:data]}\n" if hash
end

That will work as long as you get handed a hash, even if it's empty. If you're paranoid about being handed a nil:

def print_list_in_reverse(hash)
  print_list_in_reverse(hash[:next]) if hash && hash[:next]
  print "#{hash[:data]}\n" if hash
end

The other alternative is to start by checking if the current list element is nil and returning immediately in that case. Otherwise, follow the basic recursive logic outlined above. That results in the solution you provided.

Having Difficulty to Understand Variables/Pointers on Ruby LinkedList Implementation

When you're reversing a linked list, the first node becomes the last. In a singly-linked list, the last node's next pointer points to null. @head, which is initially your first node becomes the last. That's why you add the @head.next = nil.

Edit: Simulating a dry-run to better explain the problem
Assume two nodes in the linked list: 1->2

curr = @head.next  (2)
right_tmp = curr.next  (nil)
left_tmp = @head  (1)

First iteration of the while loop:

curr.next = left_tmp   ( 1 <-> 2)
left_tmp = curr     (2)
curr = right_tmp    (nil)
right_tmp = right_tmp.next unless right_tmp.nil?    (nil)

There is no second iteration since curr == nil

Now:

@head = left_tmp  (@head points to '2')

Final linked list state is:

1 <-> 2

reversing the order of an array in ruby

a = [12,16,5,9,11,5,4]
# => [12, 16, 5, 9, 11, 5, 4]
a.reverse
# => [4, 5, 11, 9, 5, 16, 12]

I'm not seeing what you're seeing.

Edit: Expanding on what Ben noticed, you may be reversing a string.

"12,16,5,9,11,5,4".reverse
# => "4,5,11,9,5,61,21"

If you have to reverse a string in that manner, you should do something like the following:

"12,16,5,9,11,5,4".split(",").reverse.join(",")
# => "4,5,11,9,5,16,12"

---

Related Topics