Skip to content

Instantly share code, notes, and snippets.

What would you like to do?
Nth Node back from END of List
# Given: 1=>2=>3=>4=>5
# Write function that takes head of list, n=2, and returns node 4 where n is distance from end
# TRICK: Need to traverse TWICE always in FORWARD direction
# 1) count index from 0 to LENGTH to find the END so we can calculate
# complement FORWARD distance!
# 2) traverse counting from 0 to (LENGTH - n) to return reference to node!
# CAREFUL: => Need to handle out-of-bounds on BOTH LOWER, and HIGHER end List
# and since this deals with (LENGTH - n), this translates to
# INVERSE releationship to detect HIGHER, LOWER bounds!
# => NODE VALUE vs otherwise
# => increment curr = at end of loop!
# => exit while on multiple conditions, needs check AFTER end of loop
# => while needs condition INITIALIZATION
class Node:
def __init__(self, value=None, next=None):
self.value = value = next
def __repr__(self):
return 'Node: {}'.format(self.value)
myNode = Node(3)
def getNthNodeBack(headSLL, n):
# LOOP 1: find the END
currNode = headSLL
idx = 0
while currNode:
idx += 1
currNode =
# exit when at one position AFTER last node,
# or LAST_INDEX is (LENGTH - 1),
# or LENGTH is (LAST_INDEX + 1)
length = idx + 1
# CALCULATE: target index at (LENGTH - n)
targetIdx = length - n
# VALIDATE input var makes sense for data
if (length <= 0):
raise Exception("Data list must have at least one element!")
if (targetIdx < 0):
raise Exception("N is too large for this data length and would index out of lower bound.")
elif (targetIdx >= length):
raise Exception("N is too small for this data length and would index out of upper bound.")
# LOOP2: find the TARGET node
currNode = headSLL
idx = 0
# ATTN: WHILE conditions are to hold VALID state, otherwise,
# failure states exit after while loop and need to distinguish between them
# - @LAST node where next is None, ptr is to Node and not None
# - @(idx > targetIdx) i.e. continue while the opposite is true
while ( and (idx < targetIdx)):
idx += 1
currNode =
# EXIT CONDITIONS: to handle
if (idx != targetIdx):
raise Exception("Reached end of Data List prior to (LENGTH - N) where N exceeds Data length.")
return currNode
headNode = Node(1)
currNode = headNode
for i in range(2,5):
currNode = Node(i)
currNode =
n = 2
targetValue = getNthNodeBack(headNode, n)
# EXPECT value 4 for index 3
n = 5
targetValue = getNthNodeBack(headNode, n)
# EXPECT value 1 for index 0
n = 0
targetValue = getNthNodeBack(headNode, n)
# EXPECT exception for out of bounds HI
n = 6
# targetValue = getNthNodeBack(headNode, n)
# EXPECT exception for out of bounds LO
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.