To complete this challenge, you need to traverse through each adjacent odd/even pair of nodes, pair by pair. In each step, you adjust the current odd node's next_node property to point to the next odd node in the list, and the current even node's next_node property to the next even node in the list.

This effectively creates two separate lists: one containing the odd nodes and the other containing the even nodes. Finally, when the end of the list is reached, the next_node property of the last odd node is then set to the first even node, which combines the two lists with the odd nodes first.

def reorder_linked_list
  # if the list is empty, no need to continue
  return if head.nil?

  # set odd to the first odd node and even to the first even node
  odd = head
  even = head.next_node

  # keep a reference to the first even node
  even_head = even

  while even && even.next_node
    # change odd's next_node property to point to the next odd node
    odd.next_node = even.next_node

    # reset the odd variable to that node
    odd = odd.next_node

    # change even's next_node property to point to the node after
    # the new odd node, i.e., the next even node
    even.next_node = odd.next_node

    # reset the even variable to that node
    even = even.next_node
  end

  # change the next_node property of the last odd node to point to the first even node
  odd.next_node = even_head
end

We start by setting our odd pointer variable to the head and even to the first even node, odd.next_node. We also save a reference to the first even node in even_head:

Because even and even.next both exist we enter the loop.

First, we change odd.next to point to the next odd node, even.next. We also move our odd pointer to point to that node:

We then repeat the process for the even node:

even and even.next still both exist so our loop continues.

Next, we again change odd.next to point to the next odd node and point odd to that node:

When we repeat the process for even, there is no odd.next so even.next and even are set to nil, ending the loop:

Finally, we set odd.next to even_head:

In the end, our linked_list looks like this:

Time: O(n)
Space: O(1)

Time: we traverse the linked list once, giving a time complexity of O(n).

Space: The extra variables we are using here are our two pointers, odd and even, and the head_even variable, which stores the value of the first even node. None of these variables grow with the size of the input so the space complexity is O(1).

This solution uses what's known as a two-pointer approach. We use two separate pointers: odd points to the current odd node and even points to the current even node. We traverse through the linked list by moving each pointer two steps at a time.

A two-pointer approach can be used to reverse a string or an array:

def reverse_the_string(str)
  i = 0
  j = str.length - 1
  while i < str.length / 2
    temp = str[i]
    str[i] = str[j]
    str[j] = temp
    i += 1
    j -= 1
  end
  str
end

reverse_the_string('abcde')
# => "edcba"

Ruby allows a shortcut for swapping characters or array elements that avoids creating a temporary variable and shortens the swap to a single line:

def reverse_the_string(str)
  i = 0
  j = str.length - 1
  while i < str.length / 2
    str[i], str[j] = str[j], str[i]
    i += 1
    j -= 1
  end
  str
end

A two-pointer approach can also be used to find the midpoint of a string or array. This approach uses what is generally referred to as a "slow" pointer and a "fast" pointer:

def find_midpoint(arr)
  slow = 0
  fast = 0
  while fast < arr.length - 1
    slow += 1
    fast += 2
  end
  arr[slow]
end

find_midpoint([1, 2, 3, 4, 5])
# => 3

When the "fast" pointer reaches the end of the array or string, the "slow" pointer is at the halfway point.

If the input array contains an even number of elements, the method returns the first element in the second half of the array:

find_midpoint([1, 2, 3, 4, 5, 6])
# => 4

Note: this same technique can be used to find the middle node in a linked list.

There are many other problems for which the two-pointer technique can be used. As you gain experience working on algorithms, you will get better at recognizing when the two-pointer technique might be helpful.