Skip to content

Instantly share code, notes, and snippets.

Embed
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 = curr.next 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
self.next = next
def __repr__(self):
return 'Node: {}'.format(self.value)
myNode = Node(3)
print(myNode)
def getNthNodeBack(headSLL, n):
# LOOP 1: find the END
currNode = headSLL
idx = 0
while currNode:
idx += 1
currNode = currNode.next
# exit when at one position AFTER last node,
# or LAST_INDEX is (LENGTH - 1),
# or LENGTH is (LAST_INDEX + 1)
length = idx + 1
print(length)
# CALCULATE: target index at (LENGTH - n)
targetIdx = length - n
print(targetIdx)
# 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 (currNode.next and (idx < targetIdx)):
idx += 1
currNode = currNode.next
print(idx)
# EXIT CONDITIONS: to handle
if (idx != targetIdx):
raise Exception("Reached end of Data List prior to (LENGTH - N) where N exceeds Data length.")
else:
return currNode
# TEST DRIVER SCRiPT:
headNode = Node(1)
currNode = headNode
for i in range(2,5):
currNode = Node(i)
currNode = currNode.next
print("*****")
n = 2
targetValue = getNthNodeBack(headNode, n)
# EXPECT value 4 for index 3
print(targetValue)
print("*****")
n = 5
targetValue = getNthNodeBack(headNode, n)
# EXPECT value 1 for index 0
print(targetValue)
print("*****")
n = 0
targetValue = getNthNodeBack(headNode, n)
# EXPECT exception for out of bounds HI
print(targetValue)
print(targetValue)
print("*****")
n = 6
# targetValue = getNthNodeBack(headNode, n)
# EXPECT exception for out of bounds LO
print(targetValue)
print("*****")
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.