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



Thanks for feedback.



Read More....
Clone a Linked List
Find the middle of linked list with odd no of nodes
Check if linked list nodes form a palindrome
Delete a node at specific position from linked list
Delete a node from linked list
Detect if cycle is present in a linked list