How to reverse a linked list in Ruby

Question

In the mutation example below, I don't understand how the linked list is reversed.

class LinkedListNode
  attr_accessor :value, :next_node

  def initialize(value, next_node=nil)
    @value = value
    @next_node = next_node
  end
end

def print_values(list_node)
  print "#{list_node.value} --> "
  if list_node.next_node.nil?
    print "nil\n"
    return
  else
    print_values(list_node.next_node)
  end
end
def reverse_list(list, previous=nil)
  current_head = list.next_node
  list.next_node = previous
  if current_head
    reverse_list(current_head, list)
  else
    list
  end
end

node1 = LinkedListNode.new(37)
node2 = LinkedListNode.new(99, node1)
node3 = LinkedListNode.new(12, node2)
print_values(node3)
puts "-------"
revlist = reverse_list(node3)
print_values(revlist)

If I just return current_head, I get 99->37->nil, which makes sense because 99 would be next_node. Returning the next line,

list.next_node = previous

throws an error because print_values method can't print the value for nil. I'm not understanding what is reversing the list. If anyone could explain this to me, I would appreciate it.

Just run the algorithm manually. With pen and paper. Tracing states of nodes. You'll see. — Sergio Tulentsev, Dec 23 '15 at 21:25

Sergio Tulentsev · Accepted Answer · 2016-01-05T09:10:42.523

5

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 
                   ^

edited Jan 05 '16 at 09:10

answered Dec 23 '15 at 21:58

Sergio Tulentsev

226,338
43
373
367

Anthony, did it help? :) Now do you see what's happening there? – Sergio Tulentsev Dec 24 '15 at 12:51
Great visualization, it wasn't so much that I didn't understand how the pointers were being rearranged, I didn't understand what the reverse_list code was doing. You both gave great answers! Thanks a lot. – Anthony D Dec 24 '15 at 12:52
1

Seeing your answer while reading through Pierres answer really helped. Once I understood it I decided to try an iterative solution instead of recursion, just to solidify things. – Anthony D Dec 24 '15 at 12:57

Pierre Michard · Answer 2 · 2015-12-23T21:51:42.200

3

# Create a LinkedListNode instance with value 36
node1 = LinkedListNode.new(37)
# Create a LinkedListNode instance which next value is node1
node2 = LinkedListNode.new(99, node1)
# node2 -> node1
# Create a LinkedListNode instance which next value is node2
node3 = LinkedListNode.new(12, node2)
# node3 -> node2 -> node1

print_values(node3)
# 12 -> 99 -> 37

Fist pass into reverse_list method

reverse_list(node3)
def reverse_list(list, previous=nil)
  # set current_head to node2
  current_head = list.next_node
  # Change node3.next_node node2-->nil
  list.next_node = previous
  if current_head
    # reverse_list(node2, node3)
    reverse_list(current_head, list)
  else
    list
  end
end

Second pass into reverse_list method

reverse_list(node2, node3)
def reverse_list(list, previous=nil)
  # set current_head to node1
  current_head = list.next_node
  # Change node2.next_node node1-->node3
  list.next_node = previous
  if current_head
    # reverse_list(node1, node2)
    reverse_list(current_head, list)
  else
    list
  end
end

last pass into reverse_list method

reverse_list(node1, node2)
def reverse_list(list, previous=nil)
  # set current_head to nil
  current_head = list.next_node
  # Change node1.next_node nil-->node2
  list.next_node = previous
  if current_head
    reverse_list(current_head, list)
  else
    # The end, return node1
    list
  end
end

By the way linked list is not a common practice in the ruby languages (and all the languages with a garbage collector), there is generally a class (such as Array for example) which have all the functionalities and flexibility you may need.

edited Dec 23 '15 at 21:51

answered Dec 23 '15 at 21:27

Pierre Michard

1,341
1
12
16

This doesn't answer the question, does it? – Sergio Tulentsev Dec 23 '15 at 21:30
@SergioTulentsev Do you ever sleep? – Wand Maker Dec 23 '15 at 21:32
@WandMaker: I was about to :) – Sergio Tulentsev Dec 23 '15 at 21:33
you're right, it doesn't. I had not correctly understood the question – Pierre Michard Dec 23 '15 at 21:35
Yes, I understand. I'm only doing it because I have to, its part of the course I'm taking. They even told us its never rarely used, but important to understand because its a common interview question. – Anthony D Dec 23 '15 at 21:41
It took me time, but I edited my comment. As you see I just explains what does each iteration does. I don't see a clearer way to explain it. – Pierre Michard Dec 23 '15 at 21:53
@PierreMichard: check out my explanation :) – Sergio Tulentsev Dec 23 '15 at 22:04
nice, I have been searching an elegant way of explaining that. You clearly found the way :) – Pierre Michard Dec 23 '15 at 22:06
Thanks, Pierre! Great answer! – Anthony D Dec 24 '15 at 12:59
You're welcome. Tell you teacher to create a Class for Ruby instead of adapting a C class to Ruby :) – Pierre Michard Dec 24 '15 at 13:02

score 3 · Answer 3 · answered Jul 24 '16 at 16:25

Here is a simple solution if someone is looking to do this without recursion

class Node
  attr_accessor :value, :next

  def initialize(value, next_node)
    @value = value
    @next = next_node
  end
end

class LinkedList
  attr_accessor :head, :tail

  def add(value)
    if(@head.nil?)
      @head = Node.new(value, nil)
      @tail = @head
    else
      @tail.next = Node.new(value, nil)
      @tail = @tail.next
    end
  end

  def reverse(list)
    return nil if list.nil?
    prev = nil
    curr = list.head

    while(curr != nil)
      temp = curr.next
      curr.next = prev
      prev = curr
      curr = temp
    end
    list.head = prev
    list
  end

  def display(list)
    return nil if list.nil?
    curr = list.head
    arr = []
    while(curr != nil)
      arr.push(curr.value)
      curr = curr.next
    end
    p arr
  end
end

list = LinkedList.new()
list.add(1)
list.add(2)
list.add(3)

list.display(list)                #list before reversing [1,2,3]
list.display(list.reverse(list))  #list after reversing  [3,2,1]

How to reverse a linked list in Ruby

3 Answers3

Linked