Given a linked list consisting of L nodes and given a number N. The task is to find the N^{th} node from the end of the linked list.
Example 1:
Input:
N = 2
LinkedList: 1->2->3->4->5->6->7->8->9
Output: 8
Explanation: In the first example, there
are 9 nodes in linked list and we need
to find 2nd node from end. 2nd node
from end is 8.  
Example 2:
Input:
N = 5
LinkedList: 10->5->100->5
Output: -1
Explanation: In the second example, there
are 4 nodes in the linked list and we
need to find 5th from the end. Since 'n'
is more than the number of nodes in the
linked list, the output is -1.
Your Task:
The task is to complete the function getNthFromLast() which takes two arguments: reference to head and N and you need to return N^{th} from the end or -1 in case node doesn't exist.
Note:
Try to solve in a single traversal.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
1 <= L <= 10^{6}
1 <= N <= 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3

'''

	Your task is to return the data stored in

	the nth node from end of linked list.

	

	Function Arguments: head (reference to head of the list), n (pos of node from end)

	Return Type: Integer or -1 if no such node exits.



	{

		# Node Class

		class Node:

		    def __init__(self, data):   # data -> value stored in node

		        self.data = data

		        self.next = None

	}

'''

#Function to find the data of nth node from the end of a linked list

def getNthFromLast(head,n):

    #code here

Solutions:
def getNthFromLast(head, n):
	count = 0
	temp = head
	while temp:
		count += 1
		temp = temp.next
	k = count - n
	if k < 0:
		return -1
	for x in range(0, k):
		head = head.next
	return head.data


def getNthFromLast(head, n):
	fast = head
	slow = head
	for i in range(n - 1):
		if fast.next:
			fast = fast.next
		else:
			return -1
	while fast and fast.next:
		slow = slow.next
		fast = fast.next
	return slow.data


def getNthFromLast(head, n):
	nodes = []
	while head is not None:
		nodes.append(head)
		head = head.next
	if len(nodes) >= n:
		return nodes[len(nodes) - n].data
	return -1


def getNthFromLast(head, n):
	t1 = head
	while n:
		if not head:
			return -1
		head = head.next
		n -= 1
	while head:
		head = head.next
		t1 = t1.next
	return t1.data


def getNthFromLast(head, n):
	(p1, p2) = (head, head)
	while n:
		if not p1:
			return -1
		p1 = p1.next
		n -= 1
	while p1:
		p1 = p1.next
		p2 = p2.next
	return p2.data


def getNthFromLast(h, n):
	c = 0
	t = h
	while t.next is not None:
		c = c + 1
		t = t.next
	c = c - n + 1
	t = h
	while c != 0 and t.next is not None:
		t = t.next
		c = c - 1
	if c == 0:
		return t.data
	return -1


def getNthFromLast(head, n):
	nodes = []
	temp = head
	while temp != None:
		nodes.append(temp)
		temp = temp.next
	if len(nodes) >= n:
		return nodes[len(nodes) - n].data
	return -1


def getNthFromLast(head, n):
	temp1 = head
	while n:
		if not head:
			return -1
		head = head.next
		n -= 1
	while head:
		head = head.next
		temp1 = temp1.next
	return temp1.data


def getNthFromLast(head, n):
	slow = head
	fast = head
	dummy = head
	i = 0
	while dummy:
		dummy = dummy.next
		i += 1
	if i < n:
		return -1
	for i in range(n):
		fast = fast.next
	while fast:
		slow = slow.next
		fast = fast.next
	return slow.data


def getNthFromLast(head, n):
	count = 0

	def _get_length_list(head):
		count = 0
		this_node = head
		while this_node:
			this_node = this_node.next
			count += 1
		return count
	len_list = _get_length_list(head)
	target_n = len_list - n
	if target_n < 0:
		return -1
	count = 1
	this_node = head
	while count < target_n + 1:
		this_node = this_node.next
		count += 1
	return this_node.data


def get_len(head):
	l = 0
	curr = head
	while curr:
		l += 1
		curr = curr.next
	return l

def getNthFromLast(head, n):
	if n > get_len(head):
		return -1
	p1 = head
	p2 = head
	for _ in range(n):
		p1 = p1.next
	while p1:
		p1 = p1.next
		p2 = p2.next
	return p2.data


def get_len(head):
	l = 0
	curr = head
	while curr:
		l += 1
		curr = curr.next
	return l

def getNthFromLast(head, n):
	if n > get_len(head):
		return -1
	temp = head
	for i in range(get_len(head) - n):
		temp = temp.next
	return temp.data


def getNthFromLast(head, n):
	curr_node = head
	nth_node = head
	while n:
		if n and curr_node == None:
			return -1
		curr_node = curr_node.next
		n -= 1
	while curr_node:
		curr_node = curr_node.next
		nth_node = nth_node.next
	return nth_node.data


def getNthFromLast(head, n):
	count = 0
	cur = head
	while cur != None:
		count += 1
		cur = cur.next
	cur = head
	if count - n < 0:
		return -1
	for i in range(count - n):
		cur = cur.next
	return cur.data


def getNthFromLast(head, n):
	l = []
	while head != None:
		l.append(head.data)
		head = head.next
	size_ll = len(l)
	if n > size_ll:
		return -1
	return l[-n]


def getNthFromLast(head, n):
	elements = []
	elements.append(head.data)
	while head.next:
		head = head.next
		elements.append(head.data)
	if len(elements) >= n:
		return elements[-n]
	else:
		return -1


def getNthFromLast(head, n):
	c = []
	while head:
		c.append(head.data)
		head = head.next
	k = len(c)
	j = k - n
	if n > k:
		return -1
	return c[j]


def getNthFromLast(head, n):
	if not head:
		return -1
	length = 0
	cur = head
	while cur:
		length += 1
		cur = cur.next
	x = head
	if n > length:
		return -1
	for i in range(length - n):
		x = x.next
	return x.data


def getNthFromLast(head, n):
	slow = head
	fast = head
	for _ in range(n):
		if fast is None:
			return -1
		fast = fast.next
	while fast != None:
		slow = slow.next
		fast = fast.next
	return slow.data


def getNthFromLast(head, n):
	(a, b) = (head, head)
	while n:
		if not a:
			return -1
		a = a.next
		n -= 1
	while a:
		a = a.next
		b = b.next
	return b.data


def getNthFromLast(head, n):
	l = 0
	itr = head
	while itr:
		itr = itr.next
		l += 1
	if n > l:
		return -1
	itr = head
	for i in range(l - n):
		itr = itr.next
	return itr.data


def getNthFromLast(head, n):
	c = 0
	front = head
	while front is not None:
		c += 1
		front = front.next
	c = c - n
	if c < 0:
		return -1
	front = head
	while c > 0:
		front = front.next
		c -= 1
	return front.data


def getNthFromLast(head, n):
	temp = head
	length = 0
	while temp is not None:
		temp = temp.next
		length += 1
	if n > length:
		return -1
	temp = head
	for i in range(0, length - n):
		temp = temp.next
	return temp.data


def getNthFromLast(head, n):
	temp = head
	for i in range(n):
		if not temp:
			return -1
		temp = temp.next
	temp2 = head
	while temp:
		temp = temp.next
		temp2 = temp2.next
	return temp2.data


def getNthFromLast(head, n):
	ansNode = head
	curr_idx = 1
	curr = head
	if head == None:
		return -1
	while curr_idx < n:
		if curr.next == None:
			return -1
		curr_idx += 1
		curr = curr.next
	if curr.next == None:
		return ansNode.data
	while curr.next != None:
		ansNode = ansNode.next
		curr = curr.next
	return ansNode.data


def getNthFromLast(head, n):
	len = 0
	temph = head
	while temph != None:
		len = len + 1
		temph = temph.next
	if n > len:
		return -1
	x = len - n
	while head.next != None and x > 0:
		x = x - 1
		head = head.next
	return head.data


def getNthFromLast(head, n):
	if not head:
		return -1
	first = second = head
	for i in range(n):
		if not second:
			return -1
		second = second.next
	while second:
		first = first.next
		second = second.next
	return first.data


def length(head):
	count = 0
	while head:
		count += 1
		head = head.next
	return count

def getNthFromLast(head, n):
	leng = length(head)
	if n > leng:
		return -1
	count = leng - n
	curr = head
	i = 0
	while curr.next != None and i < count:
		curr = curr.next
		i += 1
	return curr.data


def getNthFromLast(head, n):
	N = 1
	p = head
	while p.next != None:
		p = p.next
		N += 1
	k = N - n + 1
	if n > N:
		return -1
	else:
		n = 1
		while n != k:
			head = head.next
			n += 1
		return head.data


def getNthFromLast(head, n):
	length = 0
	p = head
	while p != None:
		length += 1
		p = p.next
	length = length - n
	if length < 0:
		return -1
	p = head
	while length != 0:
		p = p.next
		length -= 1
	return p.data


def getNthFromLast(head, n):
	c = 0
	a = head
	while a is not None:
		c = c + 1
		a = a.next
	if c < n:
		return -1
	c = c - n
	h = head
	while c > 0:
		h = h.next
		c = c - 1
	return h.data


def getNthFromLast(head, n):
	l = head
	r = head
	length = 0
	while head:
		length += 1
		head = head.next
	if n > length:
		return -1
	while n > 0 and r:
		r = r.next
		n -= 1
	while r:
		l = l.next
		r = r.next
	return l.data


class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

def getNthFromLast(head, n):
	p1 = p2 = head
	for i in range(n):
		if not p1:
			return -1
		p1 = p1.next
	while p1:
		p1 = p1.next
		p2 = p2.next
	return p2.data


def getNthFromLast(head, n):
	lenLL = getLength(head)
	if n > lenLL:
		return -1
	s = lenLL + 1 - n
	curr = head
	i = 1
	while curr:
		if i == s:
			return curr.data
		curr = curr.next
		i += 1

def getLength(A):
	res = 0
	while A:
		res += 1
		A = A.next
	return res


def getNthFromLast(head, n):
	temp = head
	c = 0
	while temp != None:
		c += 1
		temp = temp.next
	k = c
	temp = head
	if n <= c:
		while temp != None:
			c -= 1
			if c == n - 1:
				return temp.data
			temp = temp.next
	else:
		return -1


def getNthFromLast(head, n):
	dummy = Node(None)
	dummy.next = head
	f = dummy
	s = dummy
	count = 0
	for i in range(n):
		f = f.next
		if f is None:
			return -1
	while f.next:
		f = f.next
		s = s.next
	return s.next.data


def getNthFromLast(head, n):
	slowPtr = head
	fastPtr = head
	for _ in range(nth_node):
		if fastPtr is None:
			return -1
		fastPtr = fastPtr.next
	while fastPtr is not None:
		slowPtr = slowPtr.next
		fastPtr = fastPtr.next
	return slowPtr.data


def getNthFromLast(head, n):
	counter = 1
	current = head
	while current:
		current = current.next
		counter += 1
	current = head
	target = counter - n
	counter = 1
	while counter != target:
		current = current.next
		counter += 1
		if current is None:
			return -1
	return current.data


def getNthFromLast(head, n):
	left = Node(0)
	left.next = head
	right = head
	count = 0
	curr = head
	while curr:
		count += 1
		curr = curr.next
	if n > count:
		return -1
	while n > 0 and right:
		right = right.next
		n -= 1
	while right:
		right = right.next
		left = left.next
	return left.next.data


def getNthFromLast(head, n):
	if head is None:
		return
	pt1 = head
	pt2 = head
	for i in range(n):
		if pt2 == None:
			return -1
		pt2 = pt2.next
	while pt2 is not None:
		pt1 = pt1.next
		pt2 = pt2.next
	return pt1.data


def getNthFromLast(head, n):
	if head is None or n <= 0:
		return -1
	slow_ptr = head
	fast_ptr = head
	for _ in range(n):
		if fast_ptr is None:
			return -1
		fast_ptr = fast_ptr.next
	while fast_ptr is not None:
		slow_ptr = slow_ptr.next
		fast_ptr = fast_ptr.next
	return slow_ptr.data


def getNthFromLast(head, n):
	if head is None:
		return
	count = 0
	temp = head
	while temp is not None:
		count += 1
		temp = temp.next
	N = count - n
	if N < 0:
		return -1
	curr = head
	count = 0
	while curr is not None:
		if count == N:
			return curr.data
		curr = curr.next
		count += 1


def getNthFromLast(head, n):
	node = head
	count = 0
	while node:
		count += 1
		node = node.next
	node = head
	if count < n:
		return -1
	for i in range(0, count - n):
		node = node.next
	return node.data


def getNthFromLast(head, n):
	prev = head
	if prev != None and prev.next != None:
		curr = prev.next
		prev.next = None
		while curr != None:
			nxt = curr.next
			curr.next = prev
			prev = curr
			curr = nxt
	count = 1
	while prev != None and count < n:
		prev = prev.next
		count += 1
	return prev.data if prev != None else -1


def getNthFromLast(head, n):
	fast = head
	count = 1
	while fast.next is not None:
		count += 1
		fast = fast.next
	if n > count:
		return -1
	for i in range(0, count - n):
		head = head.next
	return head.data


def getNthFromLast(head, n):
	i = head
	j = head
	while n and j:
		j = j.next
		n -= 1
	if not j:
		if n != 0:
			return -1
		return head.data
	while j.next:
		i = i.next
		j = j.next
	return i.next.data


def getNthFromLast(head, n):
	length = 0
	ptr = head
	while ptr:
		length += 1
		ptr = ptr.next
	c = 0
	n = length - n
	if n < 0:
		return -1
	ptr = head
	while c < n:
		c += 1
		ptr = ptr.next
	return ptr.data


def getNthFromLast(head, n):
	l = []
	while head != None:
		l += [head.data]
		head = head.next
	if len(l) >= n:
		return l[-n]
	else:
		return -1


def getNthFromLast(head, n):
	i = 1
	a = head
	while head.next != None and i < n:
		i += 1
		head = head.next
	if i != n:
		return -1
	else:
		while head.next != None:
			a = a.next
			head = head.next
	return a.data


def getNthFromLast(head, n):
	p1 = head
	i = 1
	while p1 and i < n:
		i += 1
		p1 = p1.next
	if p1 is None:
		return -1
	p2 = head
	while p1 and p1.next:
		p1 = p1.next
		p2 = p2.next
	return p2.data


def getNthFromLast(head, n):
	p1 = head
	p2 = head
	L = 0
	while p1:
		L += 1
		p1 = p1.next
	if n > L:
		return -1
	for i in range(L - n):
		p2 = p2.next
	return p2.data


def getNthFromLast(head, n):
	len = 0
	curr = head
	while curr:
		curr = curr.next
		len += 1
	if len < n:
		return -1
	curr = head
	for i in range(1, len - n + 1):
		curr = curr.next
	return curr.data


def getNthFromLast(head, n):
	if head is None:
		return -1
	temp = head
	length = 0
	while temp:
		length += 1
		temp = temp.next
	if length < n:
		return -1
	N = length - n
	temp1 = head
	while N != 0:
		temp1 = temp1.next
		N -= 1
	return temp1.data


def getNthFromLast(head, n):
	count = 0
	dummy = head
	while dummy:
		dummy = dummy.next
		count += 1
	count1 = 0
	if count - n < 0:
		return -1
	while head:
		if count1 == count - n:
			return head.data
		count1 += 1
		head = head.next


def getNthFromLast(head, n):
	temp = head
	if temp == None:
		return -1
	a = []
	while temp != None:
		a.append(temp.data)
		temp = temp.next
	a = a[::-1]
	if n > len(a):
		return -1
	return a[n - 1]
	temp = head
	if temp.next == None:
		return -1
	else:
		m = 1
	while temp.next != None:
		m += 1
		temp = temp.next
	c = m - n + 1
	temp = head
	if c <= 0:
		return -1
	for i in range(1, m + 1):
		if i == c:
			return temp.data
		else:
			temp = temp.next


def getNthFromLast(head, n):
	back = head
	front = head
	for _ in range(n):
		if not front:
			return -1
		front = front.next
	while front:
		front = front.next
		back = back.next
	return back.data


def getNthFromLast(head, n):
	length = 0
	curr = head
	prev = None
	while curr != None:
		temp = curr.next
		curr.next = prev
		prev = curr
		curr = temp
		length += 1
	if length < n:
		return -1
	for i in range(n - 1):
		prev = prev.next
	return prev.data


def getNthFromLast(head, n):
	curr = head
	total = 0
	while curr != None:
		total += 1
		curr = curr.next
	curr = head
	check = 0
	while curr != None:
		check += 1
		if check == total - n + 1:
			return curr.data
		curr = curr.next
	return -1


def getNthFromLast(head, n):
	iter = head
	iter1 = head
	l = 0
	while iter.next is not None:
		l = l + 1
		iter = iter.next
	if l + 1 < n:
		return -1
	i = 1
	while i < l - n + 2:
		iter1 = iter1.next
		i = i + 1
	return iter1.data


def getNthFromLast(head, n):
	l = 0
	itr = head
	while itr:
		l += 1
		itr = itr.next
	if n > l:
		return -1
	l = l - n + 1
	itr = head
	i = 1
	while i < l:
		itr = itr.next
		i += 1
	return itr.data


def getNthFromLast(head, n):
	len_lst = 0
	next_node = head
	while next_node:
		next_node = next_node.next
		len_lst += 1
	counter = 1
	x = len_lst - n + 1
	next_node = head
	while next_node:
		if counter == x:
			return next_node.data
		next_node = next_node.next
		counter += 1
	return -1


def getNthFromLast(head, n):
	arr = []
	cur = head
	while cur:
		arr.append(cur.data)
		cur = cur.next
	if n > len(arr):
		return -1
	return arr[-n]


def getNthFromLast(head, n):
	curr = head
	while curr is not None and n != 0:
		curr = curr.next
		n -= 1
	if n != 0:
		return -1
	prev = head
	while curr is not None:
		curr = curr.next
		prev = prev.next
	return prev.data


def getNthFromLast(head, n):
	front = head
	back = head
	while front:
		if n == 0:
			break
		front = front.next
		n -= 1
	if n > 0:
		return -1
	while front != None:
		back = back.next
		front = front.next
	return back.data


def getNthFromLast(head, n):
	p = head
	q = head
	for i in range(n):
		if p is None:
			return -1
		p = p.next
	while p != None:
		p = p.next
		q = q.next
	return q.data


def getNthFromLast(head, n):
	cur = head
	prev = None
	x = 0
	while cur:
		temp = cur.next
		cur.next = prev
		prev = cur
		cur = temp
		x += 1
	if n > x:
		return -1
	while n != 1 and prev:
		prev = prev.next
		n -= 1
		flag = True
	return prev.data


def getNthFromLast(head, n):
	temp = head
	total_nodes = 0
	while temp:
		temp = temp.next
		total_nodes += 1
	if n > total_nodes:
		return -1
	temp = head
	for _ in range(total_nodes - n):
		temp = temp.next
	return temp.data


def getNthFromLast(head, n):
	arr = []
	curr = head
	while curr.next:
		arr.append(curr.data)
		curr = curr.next
	arr.append(curr.data)
	if len(arr) < n:
		return -1
	else:
		return arr[-n]


def getNthFromLast(head, n):
	List = []
	Length = 0
	node = head
	while node != None:
		List.append(node.data)
		node = node.next
		Length = Length + 1
	if n > Length:
		return -1
	else:
		return List[-n]


def getNthFromLast(head, n):
	curr = head
	save = head
	while curr != None:
		if n > 0:
			curr = curr.next
			n -= 1
		else:
			save = save.next
			curr = curr.next
	if n > 0:
		return -1
	return save.data


def getNthFromLast(head, n):
	temp = head
	c = 0
	x = 1
	while temp != None:
		c += 1
		temp = temp.next
	if c < n:
		return -1
	elif c == n:
		return head.data
	else:
		temp = head
		while x != c - n:
			x += 1
			temp = temp.next
		return temp.next.data


def getNthFromLast(head, n):
	x = head
	l = []
	while x:
		l.append(x.data)
		x = x.next
	if n <= len(l):
		return l[len(l) - n]
	return -1


def getNthFromLast(ll, n):
	temp = ll
	length = 0
	while temp:
		length += 1
		temp = temp.next
	req_idx = length - n + 1
	if req_idx < 1:
		return -1
	else:
		idx = 1
		while idx <= req_idx:
			if idx == 1:
				temp_2 = ll
			else:
				temp_2 = temp_2.next
			idx = idx + 1
		return temp_2.data


def getNthFromLast(head, n):
	length = 1
	itr = head
	while itr.next != None:
		itr = itr.next
		length += 1
	itr = head
	if length - n < 0:
		return -1
	else:
		for i in range(length - n):
			itr = itr.next
		return itr.data


def getNthFromLast(head, n):
	ptr1 = ptr2 = head
	for i in range(n - 1):
		if ptr2.next:
			ptr2 = ptr2.next
		else:
			return -1
	while ptr2.next is not None:
		ptr1 = ptr1.next
		ptr2 = ptr2.next
	return ptr1.data


def getNthFromLast(head, n):
	HEAD = head
	temp = 0
	length = 0
	while head:
		length += 1
		head = head.next
	if length < n:
		return -1
	target_elm_idx = length - n
	for i in range(target_elm_idx):
		HEAD = HEAD.next
		temp = 1
	return HEAD.data


def getNthFromLast(head, n):
	c = 0
	temp = head
	l = []
	while temp is not None:
		c += 1
		l.append(temp.data)
		temp = temp.next
	if n > c:
		return -1
	n1 = len(l)
	return l[n1 - n]


def getNthFromLast(head, n):
	ptr1 = head
	ptr2 = head
	while n:
		if not ptr1:
			return -1
		ptr1 = ptr1.next
		n -= 1
	while ptr1:
		ptr1 = ptr1.next
		ptr2 = ptr2.next
	return ptr2.data


def getNthFromLast(head, n):
	i = 0
	temp = head
	while temp != None:
		temp = temp.next
		i += 1
	if i < n:
		return -1
	else:
		num = i - n
		temp = head
		j = 0
		while j < num:
			temp = temp.next
			j += 1
		return temp.data


def getNthFromLast(head, n):
	index_map = dict()
	i = 1
	curr = head
	size = 0
	while curr is not None:
		index_map[i] = curr
		i += 1
		size += 1
		curr = curr.next
	if n not in index_map:
		return -1
	return index_map[size - n + 1].data


def getNthFromLast(head, n):
	size = 0
	curr = head
	while curr is not None:
		size += 1
		curr = curr.next
	if n > size:
		return -1
	m = size - n
	i = 0
	curr = head
	while i < m:
		curr = curr.next
		i += 1
	return curr.data