Function to get Nth node in a Linked List

Approach 2: Recursive Method

Using recursion involves repeatedly calling the same function, and thus, the code length is small. In terms of the previous calls, the nth recursive call can be calculated to determine the time complexity of recursion.

Consider we have Linked List as given below having elements: 20 => 76 => 54 => 76 => 20. Let's see how to find the nth node data from this LinkedList.

Algorithm

Step: 1 Create a method called getNthNode(), which has parameters of starting node and the Nth node value as getNthNode(node, value)

Step: 2 Initialize the length of the LinkedList as length=0;

Step: 3 If the head node is null, then return -1.

Step: 3 If length == value, return the data of the current node.

Step: 4. else return getNthNode(node->next,value-1)

Implementation

Code in Java

A Java program for creating a function to find the Nth Node in a Linked List.

// Node for LinkedList
class Node
{
    int data;
    Node next;
    Node(int d){ 
        data = d;  
        next = null; }
}
// class for LinkedList
class LinkedList
{
    static Node head; // head of LinkedList
    //Function to add data at the end of the LinkedList
    public void add(int new_data)
    {
        // adding the data to new_node
        Node new_node = new Node(new_data);
        // initializing the next node as head node  
        new_node.next = head;
        // Now head node is equal to the new_node  
        head = new_node;
    }
    public static void main(String[] args)
    {
        LinkedList element = new LinkedList();
        // adding elements in the LinkedList
        element.add(20);
        element.add(76);
        element.add(54);
        element.add(54);
        element.add(54);
        // Printing the Nth Node data of LinkedList by calling the getNthNode()
        System.out.printf("Nth Node data of LinkedList is :"+ getNthNode(head, 2));
    } 
    static int getNthNode(Node head, int value)
    {
        int length = 0;
        // if head node is null then return -1
        if (head == null) 
            return -1;
        // check if length of the LinkedList is equal to the index value
        if (length == value)
            return head.data;
        // move to the next node and decrease the index value by 1
        return getNthNode(head.next, value - 1);
    }
}

You can also try this code with Online Java Compiler

Run Code

Code in C++

A C++ program for creating a function to find the Nth Node in a Linked List.

#include <bits/stdc++.h> 
using namespace std; 
// Node for Linked List
class Node  
{  
    public:
    int data;  
    Node* next;  
};  
// class for creating a LinkedList
void add(Node** head_ref, int val)  
{  
    // allocating new_node
    Node* new_node =new Node(); 
    new_node->data = val;  
    new_node->next = (*head_ref);  
    (*head_ref) = new_node;  
}    
int getNthNode(struct Node* head, int value)
{
    // if head node is null then return -1
    if (head == NULL)
        return -1;
    // if index value is 0 then return data of the head node
    if (value == 0)
        return head->data;
    // move the currentPointer to the next node and decrease the index value by 1
    return getNthNode(head->next, value - 1);
}
int main(){
    struct Node* head = NULL;
    //adding elements in the linkedList
    add(&head, 20);
    add(&head, 76);
    add(&head, 54);
    add(&head, 74);
    add(&head, 64);
    //printing the Nth Node data of the LinkedList.
    printf("Nth Node data of LinkedList i: %d\n", getNthNode(head, 2));  
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Nth Node data of the LinkedList: 54

Complexity Analysis

Time Complexity: The linear search for the values takes O(n) time. 

Space Complexity: As there is no space required to store the values, it has a space complexity of O(1).

Frequently Asked Questions

Can you search a linked list easily?

The structure makes adding and removing elements in a linked list easy since you need to change the links rather than create the array; however, searching for an element in a singly linked list is very difficult and often takes O(n) time.

Which search should be used for the linked list?

A list can be searched linearly. This takes O(N). A linear search can be performed on an ordered list. The second method is also O(N), but it's twice as fast because, on average, the item you're looking for will be somewhere in the middle, and if it's not found, that's the end.

Linked lists require a lot of time to search. What can we do to reduce this time? 

Using binary search is possible if the elements of your list are sorted and your list is indexable (i.e., getting an element at position i is O(1)). It's better to get the element at the ith position in a linked list than O(N).

Conclusion

In this blog, we have seen how to create a function to get the Nth Node data of a given LinkedList.

We hope that this blog has helped you enhance your knowledge about LinkedList and if you would like to learn more, check out our articles on the link. 

Recommended Problems -

• Flattening A Linked List
• Sorted Doubly Linked List
• Linked List Cycle ii
   

You can use the Coding Ninjas Studio Guided Path to learn data structures and algorithms, programming languages, etc. Test your coding skills by participating in the Coding Ninjas Studio contests and tests! But suppose you have just started your learning process and looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problems, interview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Coding!