Skip to content

Instantly share code, notes, and snippets.

@iturgeon
Last active February 2, 2017 16:06
Show Gist options
  • Save iturgeon/e4b4bd31d7d038ba7b209259e97f4a9c to your computer and use it in GitHub Desktop.
Save iturgeon/e4b4bd31d7d038ba7b209259e97f4a9c to your computer and use it in GitHub Desktop.
Find Nth from end of a linked list
class Node
attr_accessor :nextNode, :value
def initialize(value, nextNode = nil)
@value = value
@nextNode = nextNode
end
end
def nthFromEnd(startNode, n)
rabbit = turtle = startNode
# jump rabbit ahead of turtle n nodes
while n >= 0 do
n -= 1
rabbit = rabbit.nextNode
end
# move rabbit and turtle ahead till rabbit reaches the end
while not rabbit.nil? do
rabbit = rabbit.nextNode
turtle = turtle.nextNode
end
turtle.nextNode
end
# build 10 nodes
nodes = 10.times.collect { |i| Node.new i }
# link them together
nodes.each_with_index do |node, i|
if i != 0
nodes[i-1].nextNode = node
end
end
# node values
# [0,1,2,3,4,5,6,7,8,9]
p nthFromEnd(nodes[0], 3).value # outputs 7
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment