Learn Programming and technology with ease @ developerpublish.com

HomePythonPython Program to Find Nth Node from End of Linked List

# Python Program to Find Nth Node from End of Linked List

Finding the Nth node from the end of a linked list is a common problem in computer science and programming interviews. This problem tests your understanding of linked list traversal and pointer manipulation

## Problem Statement

You are given a singly linked list containing integers, along with a positive integer N. Your task is to find and return the value of the Nth node from the end of the linked list using python.

## Python Program to Find Nth Node from End of Linked List

```class ListNode:
def __init__(self, value):
self.value = value
self.next = None

def __init__(self):

def append(self, value):
new_node = ListNode(value)
return
while current.next:
current = current.next
current.next = new_node

def find_nth_from_end(self, n):
if n <= 0 or self.head is None:
return None

for _ in range(n):
if fast_ptr is None:
return None
fast_ptr = fast_ptr.next

while fast_ptr:
slow_ptr = slow_ptr.next
fast_ptr = fast_ptr.next

return slow_ptr.value

# Example usage

n = 3  # Find the 3rd node from the end

if result is not None:
print(f"The {n}th node from the end is {result}")
else:
print("The linked list is too short.")
```

## How it Works

Step 1: Initialize Pointers We start by initializing two pointers, `slow_ptr` and `fast_ptr`, both pointing to the head of the linked list (`10`).

Step 2: Move Fast Pointer We move the `fast_ptr` N positions ahead. In this case, we move it 3 positions ahead, so it points to the node with the value `40`.

Step 3: Move Both Pointers Now, we move both the `slow_ptr` and `fast_ptr` one step at a time until the `fast_ptr` reaches the end of the linked list (`None`).

Step 4: Result At this point, the `slow_ptr` is pointing to the desired node, which is the 3rd node from the end with the value `30`.

So, by moving the `fast_ptr` N positions ahead and then moving both pointers simultaneously until the `fast_ptr` reaches the end, we can find the Nth node from the end of the linked list efficiently.

## Input/ Output

### You May Also Like

#### Python Program to Remove Duplicates from a Linked List

In this Python program, we will create a singly linked list and remove duplicate elements from it. A linked list...

#### Python Program to Solve the Celebrity Problem

This Python program solves the Celebrity Problem by finding a person who is known by everyone but does not know...

#### Python Program to Solve n-Queen Problem with Recursion

This Python program uses a recursive approach to solve the n-Queens problem. It explores all possible combinations of queen placements...