Linked List Advanced Exercises
Use the Linked List included in this document to implement the following methods. These methods are hard! Once you master these exercises you'll be an expert at Linked Lists.
Find center
Finding the center element of a linked list is a classic interview problem. First, try to produce code that can get the right answer (regardless of efficiency). Then, try to get it done in O(n) time. You can assume that the list will be odd in length.
Reverse
If you finish the find center method before we run out of time, try another classic problem, reversing a linked list.
This should be completed in O(n) time and needs to be done in place (shouldn't use any insert commands).
class Node
attr_accessor :data, :next
def initialize data
@data = data
@next = nil
end
def to_s
output = @data.to_s
output += ' > ' + @next.to_s unless @next.nil?
output
end
end
class LinkedList
attr_accessor :head, :tail
def initialize
@head = nil
@tail = nil
end
def insert_front data
temp = @head
@head = Node.new(data)
@head.next = temp
@tail = @head if @tail.nil?
end
def insert_end data
temp = @tail
@tail = Node.new(data)
temp.next = @tail unless temp.nil?
@head = @tail if @head.nil?
end
def to_s
@head.to_s
end
def get_center
#code solution for center here
end
def reverse
#bonus - code solution for reverse here
end
end
list = LinkedList.new
list.insert_front 1
list.insert_front 3
list.insert_front 5
list.insert_front 7
list.insert_front 9
#outputs: 9 > 7 > 5 > 3 > 1
puts list
#needs to output: 5
puts list.get_center.data
#needs to output: 1 > 3 > 5 > 7 > 9
list.reverse
puts list