Find Nth Node

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.

Example

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;

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

    MyLinkedList():head(NULL) {
    }
    
    void addAtHead(int val) {
        ListNode *node = new ListNode(val);
        node->next = head;
        head = node;
    }
    
    int nthNode(int n){
    	ListNode* curr = head;
    	int cnt=1;
    	while(curr){
    		if(cnt==n){
    			return curr->val;
    		}
    		curr = curr->next;
    		cnt++;
    	}
    	return -1;
    }

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

int main(){
  MyLinkedList *list = new MyLinkedList();
  list->addAtHead(10);
  list->addAtHead(7);
  list->addAtHead(4);
  list->addAtHead(2);

    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{
    
    MyLinkedList obj = new MyLinkedList();
    obj.addAtHead(10);
    obj.addAtHead(7);
    obj.addAtHead(4);
    System.out.println(obj.nthNode(3));
    
  }
  
  public static class MyLinkedList {
    
      class Node{
          Node next = null;
          int val = 0;
          
          public Node(int val){
              this.val = val;
          }
      }
      
      private Node head;
      private int size;

      public MyLinkedList() {
          this.head = null;
          this.size = 0;
      }
      
      
      public void addAtHead(int val) {
          Node node = new Node(val);
          if(this.size == 0){
              this.head = node;
          }
          else{
              node.next = this.head;
              this.head = node;
          }
          this.size++;
      }
      
      public int nthNode(int n){
      	Node curr = head;
      	int cnt=1;
      	while(curr!=null){
      		if(cnt==n){
      			return curr.val;
      		}
      		curr = curr.next;
      		cnt=cnt+1;
      	}
      	return -1;
      }

    public void printList(){
      Node curr = head;
      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.