# 5 Best Ways to Python Program to Print Nth Node from the End of a Linked List

Rate this post

π‘ Problem Formulation: This article tackles the common data structure problem: How to retrieve the nth node from the end of a singly linked list using Python. For instance, given a linked list `10->20->30->40->50` and the value of n as 2, the desired output is 40.

## Method 1: Two-Pass Algorithm

In the Two-Pass Algorithm, the first pass calculates the length of the linked list, and the second pass finds the nth node from the end by traversing to the (length-n+1)th node from the start. This method is practical when memory usage should be minimized at the cost of the extra time taken for two traversals.

Here’s an example:

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

length = 0
while temp:
temp = temp.next
length += 1
for i in range(length - n):
temp = temp.next
print(temp.data)

```

Output: 40

This code first counts the number of nodes in the linked list to calculate its length and then iterates through the list again to reach the (length-n+1)th node, printing its data. This method is straightforward but iterates through the list twice, which may not be efficient for long lists.

## Method 2: Two-Pointer Technique

The Two-Pointer Technique involves using two pointers that are placed n nodes apart. The pointers move through the list at the same speed and when the front pointer reaches the end, the other pointer will be at the nth node from the back. This method requires only one pass, making it more time-efficient than the Two-Pass Algorithm.

Here’s an example:

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

count = 0
while(count < n ):
ref_ptr = ref_ptr.next
count += 1
while(ref_ptr):
main_ptr = main_ptr.next
ref_ptr = ref_ptr.next
print(main_ptr.data)

```

Output: 40

This code snippet leverages the two-pointer method to find the nth node from the end in a single pass. The ref_ptr (reference pointer) is moved n nodes ahead of the main_ptr (main pointer). When ref_ptr reaches the end, main_ptr will be at the correct position to print its data.

## Method 3: Recursive Approach

In the Recursive Approach, the list is traversed recursively. Once the recursion hits the base condition, the counter is utilized to identify the nth node from the back on the way up the recursion stack. This method uses system stack memory and might not be suitable for very long lists due to risk of stack overflow.

Here’s an example:

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

return
counter[0] += 1
if counter[0] == n:

```

Output: 40

This recursive function traverses to the end of the list and uses a counter to print the nth node from the end. It’s an elegant solution; however, it’s not the most space-efficient due to the call stack overhead.

## Method 4: Reverse the List

Reversing the list and then traversing it to find the nth node is another approach. This solution is not recommended when the list should not be altered or when its data must be preserved in the original order.

Here’s an example:

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

prev = None
return prev

counter = 1
while counter < n:
counter += 1

```

Output: 40

After reversing the linked list, the code simply iterates n times to find the nth from end node in the original list (which is now the nth node from start). The operation is not ideal for cases where the original order is important since it alters the linked list.

## Bonus One-Liner Method 5: List Conversion

Frequently not the best solution, converting a linked list to a list allows us to leverage Python’s negative indexing to directly access the nth item from the end. This approach should only be used when memory is not a constraint and the convenience of built-in list operations is desired.

Here’s an example:

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

lst = []
return lst

print(lst[-n])