Nth Element from Last Node

Question#

Given a singly linked list, find the nth node from the last.

Example: A-B-C-D and n = 2, return C

Method 1 - Find Length and Iterate#

To find the nth element from the end, we have 2 steps:

  1. Find the length of the linked list
  2. Use a counter to count from 1 till n as we iterate the linked list
def nth_from_last(head, n):
# find the length of the linked list
curr = head
count = 1
while curr:
curr = curr.next
count += 1
if(count < n):
return
else:
curr = head
for i in range(count - n):
curr = curr.next
return curr
  • Time complexity: O(n) where n is length of linked list

Method 2 - 2 Pointers#

In this method, we use 2 pointers, p1 and p2. We start p1 from the head and p2 is at n steps ahead of p1.

We increment both pointers till p2 reaches the end of the linked list. At this point, p1 will be at the nth node from the last node of the linked list.

def nth_from_last(head, n):
# check n
if(n < 0):
return None
p1 = head
p2 = head
# increment p2
count = 0
while p2:
count += 1
if(count >= n):
break
p2 = p2.next
# n > length of list
if p2 is None:
return p2
# increment both pointers till end
while p1 and p2.next:
p1 = p1.next
p2 = p2.next
return p1.data
  • Time complexity: O(n) where n is length of linked list