Nth Node back from END of List

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("*****")