Python Program to Find the Nth Node from the End of a Linked List

Overview

This Python program finds the nth node from the end of a singly linked list. The list is traversed to locate the target node using a two-pointer technique, which efficiently solves the problem in a single pass.

Program Explanation

The structure of the program includes a Node class to represent a node in the linked list and a function to find the nth node from the end.

Steps Involved:

1. Create a class Node to represent the elements of the linked list. Each node has two attributes: data (the value of the node) and next (pointer to the next node).
2. Create a function find_nth_from_end that takes the head of a linked list and an integer n representing the position from the end.
3. Use two pointers: first and second. Start by advancing the first pointer by n steps.
4. Move both first and second pointers one step at a time until first reaches the end. The second pointer will now be at the nth node from the end.

Python Code


class Node:
"""
Node class to represent a linked list node.
Each node contains the data and a pointer to the next node.
"""
def __init__(self, data):
self.data = data
self.next = None

def find_nth_from_end(head, n):
“””
Find the nth node from the end of the linked list.

:param head: Head node of the linked list
:param n: The position from the end (1-based index)
:return: The data of the nth node from the end
“””
first = head
second = head

# Move the first pointer n steps ahead
for i in range(n):
if first is None:
return None # If n is larger than the length of the list
first = first.next

# Move both first and second pointers until first reaches the end
while first is not None:
first = first.next
second = second.next

# Now the second pointer is at the nth node from the end
return second.data

# Helper function to print a linked list
def print_linked_list(head):
“””
Print the elements of a linked list starting from the head node.

:param head: Head node of the linked list
“””
current = head
while current is not None:
print(current.data, end=” -> “)
current = current.next
print(“None”)

# Example usage:
# Create a linked list
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
head.next.next.next.next = Node(5)

print(“Original Linked List:”)
print_linked_list(head)

# Find the 2nd node from the end
n = 2
result = find_nth_from_end(head, n)
if result is not None:
print(f”The {n}th node from the end is: {result}”)
else:
print(f”The list is shorter than {n} nodes.”)

Program Explanation

This Python program defines the following:

• Node class: Each node in the linked list contains a value (data) and a reference to the next node (next).
• find_nth_from_end function: Uses two pointers to find the nth node from the end of the linked list. The first pointer is moved n steps ahead, and then both pointers are moved one step at a time until the first pointer reaches the end. The second pointer will point to the desired node.
• print_linked_list function: A utility function to display the linked list before performing the operation.

Example Output

Given the linked list:

• 1 -> 2 -> 3 -> 4 -> 5 -> None

If we are asked to find the 2nd node from the end, the output will be:

The 2nd node from the end is: 4