.png)
Nth Node from Start
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 beginning of the list (1-based indexing).
If N is greater than the length of the list or less than 1, return an appropriate indication (such as -1 or NULL depending on language).
Understanding the Core Concept
In a singly linked list:
- Nodes are connected sequentially.
- There is no direct index-based access.
- Accessing the Nth node requires traversal.
Unlike arrays:
- You cannot directly access index N.
- You must move from head step by step.
Important clarification:
Nth node from start means:
If N = 1 → head node
If N = 2 → second node
If N = length → last node
Observational Thinking Before Coding
To reach the Nth node:
- Start at head.
- Move forward N - 1 times.
- If you reach NULL before completing N - 1 moves → N is invalid.
Edge Cases:
- head is NULL
- N <= 0
- N > length
- Single node list
Approach 1: Iterative Traversal
This is the most direct and efficient method.
Algorithm
If head is NULL or N <= 0 → return invalid.
Initialize current = head
Initialize count = 1
While current is not NULL:
- If count == N → return current->data
- Move current = current->next
- Increment count
If loop ends → N is greater than length → return invalid.
Time and Space Complexity
Time Complexity: O(n)
Space Complexity: O(1)
C Implementation – Iterative
// While running this code, replace all #include "..." with #include <...>
#include "stdio.h"
#include "stdlib.h"
// Define Node
struct Node {
int data;
struct Node* next;
};
// Function to get Nth node
int getNthNode(struct Node* head, int n) {
int count = 1;
struct Node* current = head;
while (current != NULL) {
if (count == n)
return current->data;
current = current->next;
count++;
}
return -1; // invalid position
}
int main() {
// Create linked list: 10 -> 20 -> 30
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 n = 2;
int result = getNthNode(head, n);
if (result != -1)
printf("Nth node from start: %d\n", result);
else
printf("Invalid position\n");
return 0;
}Output:
Nth node from start: 20
C++ Implementation – Iterative
// 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 getNthNode(Node* head, int N) {
if (head == NULL || N <= 0)
return -1;
int count = 1;
Node* current = head;
while (current != NULL) {
if (count == N)
return current->data;
current = current->next;
count++;
}
return -1;
}
int main() {
Node* head = new Node(10);
head->next = new Node(20);
head->next->next = new Node(30);
int result = getNthNode(head, 2);
if (result != -1)
cout << "Nth node from start: " << result << endl;
else
cout << "Invalid position" << endl;
return 0;
}
Output:
Nth node from start: 20
Java Implementation – Iterative
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public class Main {
public static int getNthNode(Node head, int N) {
if (head == null || N <= 0)
return -1;
int count = 1;
Node current = head;
while (current != null) {
if (count == N)
return current.data;
current = current.next;
count++;
}
return -1;
}
public static void main(String[] args) {
Node head = new Node(10);
head.next = new Node(20);
head.next.next = new Node(30);
int result = getNthNode(head, 2);
if (result != -1)
System.out.println("Nth node from start: " + result);
else
System.out.println("Invalid position");
}
}
Output:
Nth node from start: 20
Python Implementation – Iterative
class Node:
def __init__(self, data):
self.data = data
self.next = None
def get_nth_node(head, N):
if head is None or N <= 0:
return -1
count = 1
current = head
while current:
if count == N:
return current.data
current = current.next
count += 1
return -1
head = Node(10)
head.next = Node(20)
head.next.next = Node(30)
result = get_nth_node(head, 2)
if result != -1:
print("Nth node from start:", result)
else:
print("Invalid position")
Output:
Nth node from start: 20
Approach 2: Recursive Method
Recursive logic:
If N == 1 → return head->data
Else → return result of recursive call on head->next with N - 1
Recursive Algorithm
If head is NULL → return -1
If N == 1 → return head->data
Else → return getNthNode(head->next, N - 1)
Time and Space Complexity
Time Complexity: O(n)
Space Complexity: O(n) due to recursion stack
C Implementation – Recursive
// While running this code, replace all #include "..." with #include <...>
#include "stdio.h"
#include "stdlib.h"
// Define Node FIRST
struct Node {
int data;
struct Node* next;
};
// Recursive function
int getNthNodeRecursive(struct Node* head, int N) {
if (head == NULL || N <= 0)
return -1;
if (N == 1)
return head->data;
return getNthNodeRecursive(head->next, N - 1);
}
int main() {
// Create linked list: 10 -> 20 -> 30
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 n = 3;
int result = getNthNodeRecursive(head, n);
if (result != -1)
printf("Nth node from start: %d\n", result);
else
printf("Invalid position\n");
return 0;
}
Example usage inside main:
int result = getNthNodeRecursive(head, 2);
printf("Nth node from start (Recursive): %d\n", result);
Output:
Nth node from start (Recursive): 20
C++ Implementation – Recursive
// While running this code, replace all #include "..." with #include <...>
#include "iostream"
using namespace std;
// Define Node FIRST
class Node {
public:
int data;
Node* next;
Node(int val) {
data = val;
next = NULL;
}
};
// Recursive function
int getNthNodeRecursive(Node* head, int N) {
if (head == NULL || N <= 0)
return -1;
if (N == 1)
return head->data;
return getNthNodeRecursive(head->next, N - 1);
}
int main() {
// Create linked list: 10 -> 20 -> 30
Node* head = new Node(10);
head->next = new Node(20);
head->next->next = new Node(30);
int n = 2;
int result = getNthNodeRecursive(head, n);
if (result != -1)
cout << "Nth node from start: " << result << endl;
else
cout << "Invalid position" << endl;
return 0;
}Output:
Nth node from start (Recursive): 20
Java Implementation – Recursive
public static int getNthNodeRecursive(Node head, int N) {
if (head == null || N <= 0)
return -1;
if (N == 1)
return head.data;
return getNthNodeRecursive(head.next, N - 1);
}
Output:
Nth node from start (Recursive): 20
Python Implementation – Recursive
def get_nth_node_recursive(head, N):
if head is None or N <= 0:
return -1
if N == 1:
return head.data
return get_nth_node_recursive(head.next, N - 1)
print("Nth node from start (Recursive):", get_nth_node_recursive(head, 2))
Output:
Nth node from start (Recursive): 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)
