Wednesday, May 4, 2022

Question 50 : How to find nth element from end of linked list


Algorithm for this problem would be :

  • Use two pointer firstPtr and secondPtr and initialize both to head of linkedlist
  • Move firstPtr by n-1 nodes.
  • Increment firstPtr and secondPtr until firstPtr.next not equal to null.
  • SecondPtr will be at nth from end node:

Java program for this will be 


public class LinkedList{ private Node head; private static class Node { private int value; private Node next; Node(int value) { this.value = value; } } public void addToTheLast(Node node) { if (head == null) { head = node; } else { Node temp = head; while (temp.next != null) temp = temp.next; temp.next = node; } } public void printList() { Node temp = head; while (temp != null) { System.out.format("%d ", temp.value); temp = temp.next; } System.out.println(); } public Node nthFromLastNode(Node head,int n) { Node firstPtr=head; Node secondPtr=head; for (int i = 0; i < n; i++) { firstPtr=firstPtr.next; } while(firstPtr!=null) { firstPtr=firstPtr.next; secondPtr=secondPtr.next; } return secondPtr; } public static void main(String[] args) { LinkedList list = new LinkedList(); // Creating a linked list Node head=new Node(5); list.addToTheLast(head); list.addToTheLast(new Node(6)); list.addToTheLast(new Node(7)); list.addToTheLast(new Node(1)); list.addToTheLast(new Node(2)); list.printList(); // Finding 3rd node from end Node nthNodeFromLast= list.nthFromLastNode(head,3); System.out.println("3th node from end is : "+ nthNodeFromLast.value); } }

You may also like

Kubernetes Microservices
Python AI/ML
Spring Framework Spring Boot
Core Java Java Coding Question
Maven AWS