# Find Nth Node

Difficulty Level Easy
Frequently asked in Accolite Adobe Amazon Epic Systems Factset Hike MAQ Monotype Solutions Qualcomm Snapdeal

## Problem Statement

In the “Find Nth Node” problem we have given a linked list to find the nth node. The program should print the data value in the nth node. N is the input integer index.

```3
1 2 3 4 5 6```
`3`

## Approach

Given a linked list and we have to find the n-th node. We have the pointer to the head node.  We can create a curr pointer that points to the head node, and we also take a variable to count the number of nodes we are while iterating through the linked list. Initialize the count variable to 1. In each iteration, we check if the count value is equal to the n, if it is equal to n, we return the curr->val. Otherwise, we move to the next node and increase the value of count to 1.

## Algorithm

1. Take a curr pointer points to the head node, and a count variable whose value is 1
2. Iterate through the linked list.
3. If the count value is equal to n, return the curr->val
4. Else points the curr node to its next node, and increases the value of count to 1.

## Implementation

### C++ Program to Find Nth Node

```#include<bits/stdc++.h>
using namespace std;

public:
struct ListNode {
ListNode *next;
int val;
ListNode(int a): next(NULL), val(a){}
};

}

ListNode *node = new ListNode(val);
}

int nthNode(int n){
int cnt=1;
while(curr){
if(cnt==n){
return curr->val;
}
curr = curr->next;
cnt++;
}
return -1;
}

void print_list(){
while(node){
cout<<node->val<<" ";
node = node->next;
}
cout<<endl;
}
};

int main(){

cout<<list->nthNode(3);
}```

### Java Program to Find Nth Node

```import java.util.*;
import java.lang.*;
import java.io.*;

public class Main{

public static void main (String[] args) throws java.lang.Exception{

System.out.println(obj.nthNode(3));

}

class Node{
Node next = null;
int val = 0;

public Node(int val){
this.val = val;
}
}

private int size;

this.size = 0;
}

Node node = new Node(val);
if(this.size == 0){
}
else{
}
this.size++;
}

public int nthNode(int n){
int cnt=1;
while(curr!=null){
if(cnt==n){
return curr.val;
}
curr = curr.next;
cnt=cnt+1;
}
return -1;
}

public void printList(){
while(curr!=null){
System.out.print(curr.val+" ");
curr = curr.next;
}
System.out.println("");
}

}
}```

## Complexity Analysis

### Time Complexity

O(n) where n is the given integer value. Here we visit n number of elements that take linear time.

### Space Complexity

O(1) because we don’t use any auxiliary space here.

Translate »