Linked List: Program to get the nth node in a linked list using iterative 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 iterative approach

 
Iterative Approach
  1. If head is NULL then return NULL
  2. Set the current node on head and initialize count as 1(as index is starting from 1)
  3. Traverse linked list while current is not NULL and count is less than given position
  4. While traversing, set current as current.next and increase count by 1
  5. After the loop terminates if current is not NULL then we have found the nth node so return current node
  6. Else return NULL(element with given position does not exist)
 
Complexity

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

 
Java Code
import java.util.*;

class FindNthNodeIterative {

    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 iterative approach
    public int getNthElement(int position) {
        Node current = head;
        int count = 1;
        if (head == null)
            return -1;
 
        while (current != null && count < position) {
            current = current.next;
            count++;
        }
        if (current != null)
            return current.data;
        else
            return -1;
    }
     
    public static void main(String[] args) {
        int[] linkedlistElements = new int[] { 10, 30, 50, 40, 70, 90 };
        int numberOfNodes = 6;
        // initialising object of linkedlist class
        FindNthNodeIterative ll = new FindNthNodeIterative();

        ll.buildLinkedlist(linkedlistElements, numberOfNodes);
        System.out.println("Given Linked List ");
        ll.printLinkedlist();
        
        System.out.println("Using Iterative Approach: ");
        int result = ll.getNthElement(3);
        System.out.println("Element at position 3 is: " + result);
 
    }
}

Output

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



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