find the median of all nodes in a linked list in ruby

To find the median of all nodes in a linked list, we can follow the below algorithm:

Traverse the linked list to count the total number of nodes.
Traverse the linked list again to find the middle node.
If the total number of nodes is odd, the middle node is the median.
If the total number of nodes is even, the median is the average of the middle two nodes.

Here's the ruby code to implement this algorithm:


main.rb
class Node
  attr_accessor :data, :next_node
  
  def initialize(data)
    @data = data
    @next_node = nil
  end
end

class LinkedList
  def initialize
    @head = nil
    @tail = nil
  end
  
  def add_node(data)
    new_node = Node.new(data)
    if @head.nil?
      @head = new_node
      @tail = new_node
    else
      @tail.next_node = new_node
      @tail = new_node
    end
  end
  
  def count_nodes
    count = 0
    current_node = @head
    while current_node
      count += 1
      current_node = current_node.next_node
    end
    count
  end
  
  def find_median
    count = count_nodes
    middle_node_index = (count / 2) + 1
    current_node = @head
    previous_node = nil
    median = nil
    middle_node_index.times do |i|
      if i == middle_node_index - 1
        median = current_node.data
      end
      previous_node = current_node
      current_node = current_node.next_node
    end
    if count % 2 == 0
      median = (median + previous_node.data) / 2.0
    end
    median
  end
end
1013 chars
56 lines

Example usage:


main.rb
list = LinkedList.new
list.add_node(1)
list.add_node(2)
list.add_node(3)
list.add_node(4)
list.add_node(5)

puts list.find_median #=> 3
136 chars
9 lines

In the above example, the median of the linked list [1, 2, 3, 4, 5] is 3.

similar ruby code snippets

find the median of all nodes in a linked list in ruby

find the length of a linked list in ruby

remove a node from the end of a linked list in ruby

add a node to the beginning of a linked list in ruby

remove a node from the beginning of a linked list in ruby

remove a node from the middle of a linked list in ruby

create a linked list in ruby

find the last node in a linked list in ruby

find the first node in a linked list in ruby

add a node to the end of a linked list in ruby

related categories