Write a function to get Nth node in a Linked List

Last Updated : 10 Jan, 2023

Write a GetNth() function that takes a linked list and an integer index and returns the data value stored in the node at that index position.

Example:

Input:  1->10->30->14,  index = 2
Output: 30  
The node at index 2 is 30

Algorithm:

1. Initialize count = 0
2. Loop through the link list
     a. if the count is equal to the passed index then return the current
         node
     b. Increment count
     c. change current to point to next of the current.

Implementation:

C++

// C++ program to find n'th 
// node in linked list 
#include <assert.h> 
#include <bits/stdc++.h> 
using namespace std; 
  
// Link list node 
class Node { 
public: 
    int data; 
    Node* next; 
}; 
  
/* Given a reference (pointer to 
pointer) to the head of a list 
and an int, push a new node on 
the front of the list. */
void push(Node** head_ref, int new_data) 
{ 
  
    // allocate node 
    Node* new_node = new Node(); 
  
    // put in the data 
    new_node->data = new_data; 
  
    // link the old list 
    // of the new node 
    new_node->next = (*head_ref); 
  
    // move the head to point 
    // to the new node 
    (*head_ref) = new_node; 
} 
  
// Takes head pointer of 
// the linked list and index 
// as arguments and return 
// data at index 
int GetNth(Node* head, int index) 
{ 
  
    Node* current = head; 
  
    // the index of the 
    // node we're currently 
    // looking at 
    int count = 0; 
    while (current != NULL) { 
        if (count == index) 
            return (current->data); 
        count++; 
        current = current->next; 
    } 
  
    /* if we get to this line, 
    the caller was asking 
    for a non-existent element 
    so we assert fail */
    assert(0); 
} 
  
// Driver Code 
int main() 
{ 
  
    // Start with the 
    // empty list 
    Node* head = NULL; 
  
    // Use push() to construct 
    // below list 
    // 1->12->1->4->1 
    push(&head, 1); 
    push(&head, 4); 
    push(&head, 1); 
    push(&head, 12); 
    push(&head, 1); 
  
    // Check the count 
    // function 
    cout << "Element at index 3 is " << GetNth(head, 3); 
    return 0; 
} 
  
// This code is contributed by rathbhupendra

C

// C program to find n'th 
// node in linked list 
#include <assert.h> 
#include <stdio.h> 
#include <stdlib.h> 
  
// Link list node 
struct Node { 
    int data; 
    struct Node* next; 
}; 
  
/* Given a reference (pointer to 
   pointer) to the head of a list 
   and an int, push a new node on 
   the front of the list. */
void push(struct Node** head_ref, int new_data) 
{ 
  
    // allocate node 
    struct Node* new_node 
        = (struct Node*)malloc(sizeof(struct Node)); 
  
    // put in the data 
    new_node->data = new_data; 
  
    // link the old list 
    // of the new node 
    new_node->next = (*head_ref); 
  
    // move the head to point 
    // to the new node 
    (*head_ref) = new_node; 
} 
  
// Takes head pointer of 
// the linked list and index 
// as arguments and return 
// data at index 
int GetNth(struct Node* head, int index) 
{ 
  
    struct Node* current = head; 
  
    // the index of the 
    // node we're currently 
    // looking at 
    int count = 0; 
    while (current != NULL) { 
        if (count == index) 
            return (current->data); 
        count++; 
        current = current->next; 
    } 
  
    /* if we get to this line, 
       the caller was asking 
       for a non-existent element 
       so we assert fail */
    assert(0); 
} 
  
// Driver Code 
int main() 
{ 
  
    // Start with the 
    // empty list 
    struct Node* head = NULL; 
  
    // Use push() to construct 
    // below list 
    // 1->12->1->4->1 
    push(&head, 1); 
    push(&head, 4); 
    push(&head, 1); 
    push(&head, 12); 
    push(&head, 1); 
  
    // Check the count 
    // function 
    printf("Element at index 3 is %d", GetNth(head, 3)); 
    getchar(); 
}

Java

// Java program to find n'th node in linked list 
import java.io.*; 
class Node { 
    int data; 
    Node next; 
    Node(int d) 
    { 
        data = d; 
        next = null; 
    } 
} 
  
class LinkedList { 
    Node head; // the head of list 
  
    /* Takes index as argument and return data at index*/
    public int GetNth(int index) 
    { 
        Node current = head; 
        int count = 0; /* index of Node we are 
                          currently looking at */
        while (current != null) 
        { 
            if (count == index) 
                return current.data; 
            count++; 
            current = current.next; 
        } 
  
        /* if we get to this line, the caller was asking 
        for a non-existent element so we assert fail */
        assert (false); 
        return 0; 
    } 
  
    /* Given a reference to the head of a list and an int, 
       inserts a new Node on the front of the list. */
    public void push(int new_data) 
    { 
  
        /* 1. alloc the Node and put data*/
        Node new_Node = new Node(new_data); 
  
        /* 2. Make next of new Node as head */
        new_Node.next = head; 
  
        /* 3. Move the head to point to new Node */
        head = new_Node; 
    } 
  
    /* Driver code*/
    public static void main(String[] args) 
    { 
        /* Start with empty list */
        LinkedList llist = new LinkedList(); 
  
        /* Use push() to construct below list 
           1->12->1->4->1  */
        llist.push(1); 
        llist.push(4); 
        llist.push(1); 
        llist.push(12); 
        llist.push(1); 
  
        /* Check the count function */
        System.out.println("Element at index 3 is "
                           + llist.GetNth(3)); 
    } 
}

Python3

# A complete working Python program to find n'th node 
# in a linked list 
  
# Node class 
  
  
class Node: 
    # Function to initialise the node object 
    def __init__(self, data): 
        self.data = data  # Assign data 
        self.next = None  # Initialize next as null 
  
  
# Linked List class contains a Node object 
class LinkedList: 
  
    # Function to initialize head 
    def __init__(self): 
        self.head = None
  
    # This function is in LinkedList class. It inserts 
    # a new node at the beginning of Linked List. 
  
    def push(self, new_data): 
  
        # 1 & 2: Allocate the Node & 
        #     Put in the data 
        new_node = Node(new_data) 
  
        # 3. Make next of new Node as head 
        new_node.next = self.head 
  
        # 4. Move the head to point to new Node 
        self.head = new_node 
  
    # Returns data at given index in linked list 
    def getNth(self, index): 
        current = self.head  # Initialise temp 
        count = 0  # Index of current node 
  
        # Loop while end of linked list is not reached 
        while (current): 
            if (count == index): 
                return current.data 
            count += 1
            current = current.next
  
        # if we get to this line, the caller was asking 
        # for a non-existent element so we assert fail 
        assert(false) 
        return 0
  
  
# Driver Code 
if __name__ == '__main__': 
  
    llist = LinkedList() 
  
    # Use push() to construct below list 
    # 1->12->1->4->1 
    llist.push(1) 
    llist.push(4) 
    llist.push(1) 
    llist.push(12) 
    llist.push(1) 
  
    n = 3
    print("Element at index 3 is :", llist.getNth(n)) 

C#

// C# program to find n'th node in linked list 
using System; 
using System.Diagnostics; 
  
public class Node { 
    public int data; 
    public Node next; 
    public Node(int d) 
    { 
        data = d; 
        next = null; 
    } 
} 
  
class LinkedList { 
    Node head; // the head of list 
  
    /* Takes index as argument and return data at index*/
    public int GetNth(int index) 
    { 
        Node current = head; 
        int count = 0; /* index of Node we are 
                        currently looking at */
        while (current != null) { 
            if (count == index) 
                return current.data; 
            count++; 
            current = current.next; 
        } 
  
        /* if we get to this line, the caller was asking 
        for a non-existent element so we assert fail */
        Debug.Assert(false); 
        return 0; 
    } 
  
    /* Given a reference to the head of a list and an int, 
    inserts a new Node on the front of the list. */
    public void push(int new_data) 
    { 
  
        /* 1. alloc the Node and put data*/
        Node new_Node = new Node(new_data); 
  
        /* 2. Make next of new Node as head */
        new_Node.next = head; 
  
        /* 3. Move the head to point to new Node */
        head = new_Node; 
    } 
  
    /* Driver code*/
    public static void Main(String[] args) 
    { 
        /* Start with empty list */
        LinkedList llist = new LinkedList(); 
  
        /* Use push() to construct below list 
        1->12->1->4->1 */
        llist.push(1); 
        llist.push(4); 
        llist.push(1); 
        llist.push(12); 
        llist.push(1); 
  
        /* Check the count function */
        Console.WriteLine("Element at index 3 is "
                          + llist.GetNth(3)); 
    } 
} 
  
// This code is contributed by Arnab Kundu

Javascript

<script> 
  
// Javascript program to find n'th  
// node in linked list 
  
class Node { 
    constructor(d) { 
        this.data = d; 
        this.next = null; 
    } 
} 
  
    var head; // the head of list 
  
    /* Takes index as argument and  
    return data at index */
    function GetNth(index)  
    { 
        var current = head; 
        var count = 0;  
        /* 
         index of Node we are currently looking at 
                         */
        while (current != null) { 
            if (count == index) 
                return current.data; 
            count++; 
            current = current.next; 
        } 
  
        /* 
        if we get to this line, the caller was asking 
        for a non-existent element so 
         we assert fail 
         */
        assert (false); 
        return 0; 
    } 
  
    /* 
     * Given a reference to the head of a  
       list and an int, inserts a new Node on the 
       front of the list. 
     */
    function push(new_data) { 
  
        /* 1. alloc the Node and put data */
        var new_Node = new Node(new_data); 
  
        /* 2. Make next of new Node as head */
        new_Node.next = head; 
  
        /* 3. Move the head to point to new Node */
        head = new_Node; 
    } 
  
    /* Driver code */
      
        /* Start with empty list */
  
        /* 
       Use push() to construct below 
       list 1->12->1->4->1 
         */
        push(1); 
        push(4); 
        push(1); 
        push(12); 
        push(1); 
  
        /* Check the count function */
        document.write("Element at index 3 is " 
        + GetNth(3)); 
  
// This code is contributed by todaysgaurav 
  
</script> 

Output

Element at index 3 is 4

Time Complexity: O(n)
Auxiliary Space: O(1) space created for variables

Method 2- With Recursion
This method is contributed by MY_DOOM.

Algorithm:

Algorithm
getnth(node,n)
1. Initialize count = 0
2. if count==n
     return node->data
3. else
    return getnth(node->next,n-1)

Implementation:

C++

// C++ program to find n'th node in linked list 
// using recursion 
#include <bits/stdc++.h> 
using namespace std; 
  
/* Linked list node */
struct Node { 
    int data; 
    struct Node* next; 
}; 
  
/*  Given a reference (pointer to pointer) to 
    the head of a list and an int, push a 
    new node on the front of the list. */
void push(struct Node** head_ref, int new_data) 
{ 
    /* allocate node */
    struct Node* new_node 
        = (struct Node*)malloc(sizeof(struct Node)); 
  
    /* put in the data */
    new_node->data = new_data; 
  
    /* link the old list of the new node */
    new_node->next = (*head_ref); 
  
    /* move the head to point to the new node */
    (*head_ref) = new_node; 
} 
  
/* Takes head pointer of the linked list and index 
    as arguments and return data at index. (Don't use 
   another variable)*/
int GetNth(struct Node* head, int n) 
{ 
    // if length of the list is less 
    // than the given index, return -1 
    if (head == NULL) 
        return -1; 
  
    // if n equal to 0 return node->data 
    if (n == 0) 
        return head->data; 
  
    // increase head to next pointer 
    // n - 1: decrease the number of recursions until n = 0 
    return GetNth(head->next, n - 1); 
} 
  
/* Driver code*/
int main() 
{ 
    /* Start with the empty list */
    struct Node* head = NULL; 
  
    /* Use push() to construct below list 
     1->12->1->4->1  */
    push(&head, 1); 
    push(&head, 4); 
    push(&head, 1); 
    push(&head, 12); 
    push(&head, 1); 
  
    /* Check the count function */
    printf("Element at index 3 is %d", GetNth(head, 3)); 
    getchar(); 
} 
  
// This code is contributed by Aditya Kumar (adityakumar129)

C

// C program to find n'th node in linked list 
// using recursion 
#include <stdio.h> 
#include <stdlib.h> 
  
/* Linked list node */
typedef struct Node { 
    int data; 
    struct Node* next; 
} Node; 
  
/*  Given a reference (pointer to pointer) to 
    the head of a list and an int, push a 
    new node on the front of the list. */
void push(Node** head_ref, int new_data) 
{ 
    /* allocate node */
    Node* new_node = (Node*)malloc(sizeof(Node)); 
  
    /* put in the data */
    new_node->data = new_data; 
  
    /* link the old list of the new node */
    new_node->next = (*head_ref); 
  
    /* move the head to point to the new node */
    (*head_ref) = new_node; 
} 
  
/* Takes head pointer of the linked list and index 
    as arguments and return data at index. (Don't use 
   another variable)*/
int GetNth(Node* head, int n) 
{ 
    // if length of the list is less 
    // than the given index, return -1 
    if (head == NULL) 
        return -1; 
  
    // if n equal to 0 return node->data 
    if (n == 0) 
        return head->data; 
  
    // increase head to next pointer 
    // n - 1: decrease the number of recursions until n = 0 
    return GetNth(head->next, n - 1); 
} 
  
/* Driver code*/
int main() 
{ 
    /* Start with the empty list */
    struct Node* head = NULL; 
  
    /* Use push() to construct below list 
     1->12->1->4->1  */
    push(&head, 1); 
    push(&head, 4); 
    push(&head, 1); 
    push(&head, 12); 
    push(&head, 1); 
  
    /* Check the count function */
    printf("Element at index 3 is %d", GetNth(head, 3)); 
    getchar(); 
}

Java

// Java program to find n'th node in linked list 
// using recursion 
import java.io.*; 
class GFG { 
  
    /* Linked list node */
    static class Node { 
        int data; 
        Node next; 
        Node(int data) { this.data = data; } 
    } 
  
    /* Given a reference (pointer to pointer) to 
        the head of a list and an int, push a 
        new node on the front of the list. */
    static Node push(Node head, int new_data) 
    { 
        /* allocate node */
        Node new_node = new Node(new_data); 
  
        new_node.next = head; 
  
        head = new_node; 
  
        return head; 
    } 
  
    /* Takes head pointer of the linked list and index 
        as arguments and return data at index*/
    static int GetNth(Node head, int n) 
    { 
        int count = 0; 
        if (head == null) // edge case - if head is null 
            return -1; 
        // if count equal too n return node.data 
        if (count == n) 
            return head.data; 
  
        // recursively decrease n and increase 
        // head to next pointer 
        return GetNth(head.next, n - 1); 
    } 
  
    /* Driver code*/
    public static void main(String args[]) 
    { 
        /* Start with the empty list */
        Node head = null; 
  
        /* Use push() to construct below list 
        1.12.1.4.1 */
        head = push(head, 1); 
        head = push(head, 4); 
        head = push(head, 1); 
        head = push(head, 12); 
        head = push(head, 1); 
  
        /* Check the count function */
        System.out.printf("Element at index 3 is %d", 
                          GetNth(head, 3)); 
    } 
} 
// This code is contributed by Arnab Kundu

Python3

# Python3 program to find n'th node in 
# linked list using recursion 
  
  
class Node: 
    def __init__(self, data): 
        self.data = data 
        self.next = None
  
  
class LinkedList: 
    def __init__(self): 
        self.head = None
  
    ''' Given a reference (pointer to pointer) to the 
        head of a list and an int, push a new node on 
        the front of the list. '''
  
    def push(self, new_data):  # make new node and add 
                              # into LinkedList 
        new_node = Node(new_data) 
        new_node.next = self.head 
        self.head = new_node 
  
    def getNth(self, llist, position): 
  
        # call recursive method 
        llist.getNthNode(self.head, position, llist) 
  
    # recursive method to find Nth Node 
    def getNthNode(self, head, position, llist): 
        count = 0  # initialize count 
        if(head): 
            if count == position:  # if count is equal to position, 
                                  # it means we have found the position 
                print(head.data) 
            else: 
                llist.getNthNode(head.next, position - 1, llist) 
        else:  # if head doesn't exist we have 
              # traversed the LinkedList 
            print('Index Doesn\'t exist') 
  
  
# Driver Code 
if __name__ == "__main__": 
    llist = LinkedList() 
    llist.push(1) 
    llist.push(4) 
    llist.push(1) 
    llist.push(12) 
    llist.push(1) 
    # llist.getNth(llist,int(input())) 
    # Enter the node position here 
    # first argument is instance of LinkedList 
  
    print("Element at Index 3 is", end=" ") 
    llist.getNth(llist, 3) 
  
# This code is contributed by Yogesh Joshi 

C#

// C# program to find n'th node in 
// linked list using recursion 
using System; 
  
class GFG { 
  
    /* Link list node */
    public class Node { 
        public int data; 
        public Node next; 
        public Node(int data) { this.data = data; } 
    } 
  
    /* Given a reference (pointer to pointer) to 
        the head of a list and an int, push a 
        new node on the front of the list. */
    static Node push(Node head, int new_data) 
    { 
        /* allocate node */
        Node new_node = new Node(new_data); 
  
        /* put in the data */
        new_node.data = new_data; 
  
        new_node.next = head; 
  
        head = new_node; 
  
        return head; 
    } 
  
    /* Takes head pointer of the linked list and index 
        as arguments and return data at index*/
    static int GetNth(Node head, int n) 
    { 
        // Base Condition 
        if (head == null) 
            return -1; 
  
        int count = 0; 
  
        // if count equal too n return node.data 
        // Test Condition 
        if (count == n) 
            return head.data; 
  
        // recursively decrease n and increase 
        // head to next pointer 
        return GetNth(head.next, n - 1); 
    } 
  
    /* Driver code*/
    public static void Main() 
    { 
        /* Start with the empty list */
        Node head = null; 
  
        /* Use push() to construct below list 
        1.12.1.4.1 */
        head = push(head, 1); 
        head = push(head, 4); 
        head = push(head, 1); 
        head = push(head, 12); 
        head = push(head, 1); 
  
        /* Check the count function */
        Console.Write("Element at index 3 is {0}", 
                      GetNth(head, 3)); 
    } 
} 
/*Code improvement by Aishwarya Mittal*/
/* This code contributed by PrinciRaj1992 */

Javascript

<script> 
// javascript program to find n'th node in linked list 
// using recursion    /* Link list node */ 
class Node { 
    constructor(val) { 
        this.data = val; 
        this.next = null; 
    } 
} 
  
    /* 
     * Given a reference (pointer to pointer) to the head of a list and an int, push 
     * a new node on the front of the list. 
     */
    function push(head , new_data) { 
        /* allocate node */
var new_node = new Node(new_data); 
  
        /* put in the data */
        new_node.data = new_data; 
  
        new_node.next = head; 
  
        head = new_node; 
  
        return head; 
    } 
  
    /* 
     * Takes head pointer of the linked list and index as arguments and return data 
     * at index 
     */
    function GetNth(head , n) { 
        var count = 0; 
        if (head == null) // edge case - if head is null 
            return -1; 
        // if count equal too n return node.data 
        if (count == n) 
            return head.data; 
  
        // recursively decrease n and increase 
        // head to next pointer 
        return GetNth(head.next, n - 1); 
    } 
  
    /* Driver code */
      
        /* Start with the empty list */
var head = null; 
  
        /* 
         * Use push() to construct below list 1.12.1.4.1 
         */
        head = push(head, 1); 
        head = push(head, 4); 
        head = push(head, 1); 
        head = push(head, 12); 
        head = push(head, 1); 
  
        /* Check the count function */
        document.write("Element at index 3 is ", GetNth(head, 3)); 
  
// This code contributed by gauravrajput1  
</script> 

Output

Element at index 3 is 4

Time Complexity : O(n)
Auxiliary Space: O(n) due to recursive calls.

Suggest improvement

Write a function to delete a Linked List

Program for Nth node from the end of a Linked List

Share your thoughts in the comments

Types of Linked List

Basic operations on Linked List

Easy problems on Linked List

Medium problems on Linked List

Hard problems on Linked List

Types of Linked List

Basic operations on Linked List

Easy problems on Linked List

Medium problems on Linked List

Hard problems on Linked List

Write a function to get Nth node in a Linked List

C++

C

Java

Python3

C#

Javascript

C++

C

Java

Python3

C#

Javascript

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?