.png)
Nth Node from End
Problem Statement
Given the head pointer of a singly linked list and a positive integer N, return the data of the Nth node from the end of the list (1-based indexing from the end).
If N is greater than the length of the list or less than or equal to zero, return an invalid indicator (such as -1 depending on the language).
Understanding the Concept Clearly
Nth node from end means:
If list is:
10 → 20 → 30 → 40 → 50
Length = 5
If N = 1 → answer is 50
If N = 2 → answer is 40
If N = 5 → answer is 10
If N > 5 → invalid
Important clarification:
Nth from end is different from:
- Nth from start
- (Length - N + 1)th from start (though logically related)
Observational Thinking Before Coding
There are two major ways to solve this:
Two-pass approach
Single-pass two-pointer approach
The second approach is preferred in interviews because it is more optimal in practice.
Approach 1: Two-Pass Method
Idea
Step 1: Find the length of the list.
Step 2: Calculate position from start:
Position = Length - N + 1
Step 3: Traverse again to that position.
Algorithm
If head is NULL or N <= 0 → return invalid.
Find total length L.
If N > L → return invalid.
Compute position = L - N + 1.
Traverse to that position and return data.
Time and Space Complexity
Time Complexity: O(n)
Space Complexity: O(1)
Requires two traversals.
C Implementation
// While running this code, replace all #include "..." with #include <...>
#include "stdio.h"
#include "stdlib.h"
struct Node {
int data;
struct Node* next;
};
int getLength(struct Node* head) {
int count = 0;
while (head != NULL) {
count++;
head = head->next;
}
return count;
}
int getNthFromEnd(struct Node* head, int N) {
if (head == NULL || N <= 0)
return -1;
int length = getLength(head);
if (N > length)
return -1;
int position = length - N + 1;
int count = 1;
while (head != NULL) {
if (count == position)
return head->data;
head = head->next;
count++;
}
return -1;
}
int main() {
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
head->data = 10;
head->next = (struct Node*)malloc(sizeof(struct Node));
head->next->data = 20;
head->next->next = (struct Node*)malloc(sizeof(struct Node));
head->next->next->data = 30;
head->next->next->next = NULL;
int result = getNthFromEnd(head, 2);
if (result != -1)
printf("Nth node from end: %d\n", result);
else
printf("Invalid position\n");
return 0;
}Output:
Nth node from end: 20
C++ Implementation
// While running this code, replace all #include "..." with #include <...>
#include "iostream"
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int val) {
data = val;
next = NULL;
}
};
int getLength(Node* head) {
int count = 0;
while (head != NULL) {
count++;
head = head->next;
}
return count;
}
int getNthFromEnd(Node* head, int N) {
if (head == NULL || N <= 0)
return -1;
int length = getLength(head);
if (N > length)
return -1;
int position = length - N + 1;
int count = 1;
while (head != NULL) {
if (count == position)
return head->data;
head = head->next;
count++;
}
return -1;
}
int main() {
Node* head = new Node(10);
head->next = new Node(20);
head->next->next = new Node(30);
int result = getNthFromEnd(head, 2);
if (result != -1)
cout << "Nth node from end: " << result << endl;
else
cout << "Invalid position" << endl;
return 0;
}Output:
Nth node from end: 20
Approach 2: Single-Pass Two-Pointer Technique
This is the most important approach for interviews.
Core Idea
Maintain two pointers:
- First pointer advances N steps ahead.
- Second pointer starts from head.
Once first pointer reaches the end:
- Second pointer will be at the Nth node from end.
Why This Works
Distance between first and second pointer remains N.
When first reaches NULL, second is exactly N nodes behind.
Algorithm
If head is NULL or N <= 0 → return invalid.
Initialize first = head
Initialize second = head
Move first pointer N steps forward.
If first becomes NULL before N steps → N > length → invalid.
Now move both first and second until first reaches NULL.
Return second->data.
Time and Space Complexity
Time Complexity: O(n)
Space Complexity: O(1)
Only one traversal.
C Implementation
// While running this code, replace all #include "..." with #include <...>
#include "stdio.h"
#include "stdlib.h"
struct Node {
int data;
struct Node* next;
};
int getNthFromEndOptimized(struct Node* head, int N) {
if (head == NULL || N <= 0)
return -1;
struct Node* first = head;
struct Node* second = head;
for (int i = 0; i < N; i++) {
if (first == NULL)
return -1;
first = first->next;
}
while (first != NULL) {
first = first->next;
second = second->next;
}
return second->data;
}
int main() {
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
head->data = 10;
head->next = (struct Node*)malloc(sizeof(struct Node));
head->next->data = 20;
head->next->next = (struct Node*)malloc(sizeof(struct Node));
head->next->next->data = 30;
head->next->next->next = NULL;
int result = getNthFromEndOptimized(head, 2);
printf("Nth node from end (Optimized): %d\n", result);
return 0;
}Example usage:
int result = getNthFromEndOptimized(head, 2);
printf("Nth node from end (Optimized): %d\n", result);
Output:
Nth node from end (Optimized): 20
C++ Implementation
// While running this code, replace all #include "..." with #include <...>
#include "iostream"
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int val) {
data = val;
next = NULL;
}
};
int getNthFromEndOptimized(Node* head, int N) {
if (head == NULL || N <= 0)
return -1;
Node* first = head;
Node* second = head;
for (int i = 0; i < N; i++) {
if (first == NULL)
return -1;
first = first->next;
}
while (first != NULL) {
first = first->next;
second = second->next;
}
return second->data;
}
int main() {
Node* head = new Node(10);
head->next = new Node(20);
head->next->next = new Node(30);
int result = getNthFromEndOptimized(head, 2);
cout << "Nth node from end (Optimized): " << result << endl;
return 0;
}Output:
Nth node from end (Optimized): 20
Java Implementation
public static int getNthFromEndOptimized(Node head, int N) {
if (head == null || N <= 0)
return -1;
Node first = head;
Node second = head;
for (int i = 0; i < N; i++) {
if (first == null)
return -1;
first = first.next;
}
while (first != null) {
first = first.next;
second = second.next;
}
return second.data;
}
Output:
Nth node from end (Optimized): 20
Python Implementation
def get_nth_from_end_optimized(head, N):
if head is None or N <= 0:
return -1
first = head
second = head
for _ in range(N):
if first is None:
return -1
first = first.next
while first:
first = first.next
second = second.next
return second.data
print("Nth node from end (Optimized):", get_nth_from_end_optimized(head, 2))
Output:
Nth node from end (Optimized): 20
Next problem in the series:
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.jpg)
.png)
.jpg)
.jpg)
.jpg)
