Last active
February 2, 2017 16:06
-
-
Save iturgeon/e4b4bd31d7d038ba7b209259e97f4a9c to your computer and use it in GitHub Desktop.
Find Nth from end of a linked list
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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