Linked List: Program to get the nth node in a linked list using recursive approach

Write a program to find the node in the nth position in a linked list

Linked list is a series of nodes in which each node contains a data field and
reference (pointer) to the next node in the list.

In this article we find the nth node in a given linked list. We solve this using the recursive approach

Recursive Approach

In this approach we simply traverse till position using recursion and return elements

1. Initialise count as one and check if head is then return NULL
2. If count is equal to position return head.data,else call function again with passing head.next and given position-1

Complexity

Time Complexity : O(n) , where n is the size of linked list
Space Complexity : O(n)

Java Code

import java.util.*;
  
class FindNthNodeRecursive {

    class Node {
        // initialising data field and next pointer of node
        int data;
        Node next;
     
        Node(int d) {
            this.data = d;
            this.next = null;
        }
    }

    Node head;
 
    // creating a linked list using array
    public void buildLinkedlist(int startingNodeArray[], int noOfNodes) {
        int i;
        Node temp, last;
        temp = new Node(startingNodeArray[0]);
        temp.next = null;
        head = temp;
        last = temp;
        for (i = 1; i < noOfNodes; i++) {
            temp = new Node(startingNodeArray[i]);
            temp.next = null;
            last.next = temp;
            last = temp;
        }
    }
     
        // printing of linkedList
    public void printLinkedlist() {
        List allNodesList = new ArrayList<>();
        Node temp = head;
        while (temp != null) {
            allNodesList.add(Integer.toString(temp.data));
            temp = temp.next;
        }
        System.out.println(String.join(" -> ", allNodesList));
 
    }
 
    // getting nth element using recursive approach
    public int getNthElementRecursive(Node head, int position) {
        int count = 1;
        if (head == null)
            return -1;
 
        if (count == position)
            return head.data;
 
        return getNthElementRecursive(head.next, position - 1);
    }
     
    public static void main(String[] args) {
        int[] linkedlistElements = new int[] { 10, 30, 50, 40, 70, 90 };
        int numberOfNodes = 6;
        
        FindNthNodeRecursive ll = new FindNthNodeRecursive();
        
        ll.buildLinkedlist(linkedlistElements, numberOfNodes);
        System.out.println("Given Linked List ");
        ll.printLinkedlist();

        System.out.println("Using Recursive Approach ");
        int Element = ll.getNthElementRecursive(ll.head, 5);
        System.out.println("Element at position 5 is: " + Element);
 
    }
}

Output

Given Linked List 
10 -> 30 -> 50 -> 40 -> 70 -> 90
Using Recursive Approach 
Element at position 5 is: 70