In my previous article, we implemented a linked list data structure with some very basic operations. While those operations are useful in many cases, they won’t take us very far. That’s is why in this (and subsequent) post we’ll talk about more advanced actions we can perform on our linked lists.

Reverse a linked list

Let’s say we have a linked list with elements 1,2,3,4. As you remember, each element points to the next one while the last one points to nil.

Now, how can we reverse a linked list? Let’s take a look at one of the iterative solutions:

Iterative reversal

# class definition skipped for brevity

def reverse
  node = head
  previous = nil

  while node
    next_node = node.next
    node.next = previous
    previous = node
    node = next_node
  end

  self.head = previous
end

# For simplicity sake, I will represent the result as an array

list # [1, 2, 3, 4]
list.reverse # [4, 3, 2, 1]

We have lots of pointers and temporary variables pointing back and forth! Let’s figure out what happens on each iteration.

Iteration 1:

We are not at the end of our list (node is [1, 2, 3, 4]). Continue!

next_node = [2, 3, 4]
node.next = nil
previous = [1]
node = [2, 3, 4]

Iteration 2

We are not at the end of our list (node is [2, 3, 4]). Continue!

next_node = [3, 4]
node.next = [1]
previous = [2, 1]
node = [3, 4]

Iteration 3

We are not at the end of our list (node is [3, 4]). Continue!

next_node = [4]
node.next = [2, 1]
previous = [3, 2, 1]
node = [4]

Iteration 4

We are not at the end of our list (node is [4]). Continue!

next_node = nil
node.next = [3, 2, 1]
previous = [4, 3, 2, 1]
node = nil

Iteration 5

We are at the end of our list (node is nil). Break!

We then point head toprevious (which we used to store our reversed list) and it’s done!

Recursive reversal

So now you understand the iterative approach to this problem. How about a recursive one?

It is useful to understand how the call stack works. Please take a look at the following article for details.

In this example, let’s assume that head points to the linked list with values 1, 2, 3, 4.

def reverse(node = head, previous = nil)
  if !node
    return self.head = previous
  else
    next_node = node.next
    node.next = previous
    reverse(next_node, node)
  end
end

Again, let’s decipher what happens on each recursive call to reverse method. To make it more transparent, I’ll show the arguments of each new recursive call.

Call 1

We are not at the end of our list (node is [1, 2, 3, 4]). Continue!

next_node = [2, 3, 4]
node.next = nil
reverse([2, 3, 4], [1])

Since our previous node is set to nil by default, we cut off everything AFTER our list’s first element => [1].

Call 2

We are not at the end of our list (node is [2, 3, 4]). Continue!

next_node = [3, 4]
node.next = [1]
reverse([3, 4], [2, 1])

Inside this call, we slice (shift one step to the right) our list and assign it to next_node. Then we take our initial (for this call) list ([2, 3, 4]) and set its next element to previous ([1]). As a result, the second argument for the next recursive call becomes [2, 1]

Call 3

We are not at the end of our list (node is [3, 4]). Continue!

next_node = [4]
node.next = [2, 1]
reverse([4], [3, 2, 1])

The description is the same:

initial list - [3, 4]
next_node - [4]
node.next - [2, 1]
node - [3, 2, 1]

Call 4

We are not at the end of our list (node is [4]). Continue!

next_node = nil
node.next = [3, 2, 1]
reverse_rec(nil, [4, 3, 2, 1])

The description is the same:

initial list - [4]
next_node - nil
node.next - [3, 2, 1]
node - [4, 3, 2, 1]

Call 5

We are at th end of our list (node is nil). Break!

Since our current node is now nil, we’ll set the head of our initial linked list to previous, which is our list in reverse!