Table of Contents
This is one of popular interview question.
Java Linked List Interview Programs:
- How to reverse a linked list in java
- How to reverse a linked list in pairs
- How to find middle element of linked list in java
- How to detect a loop in linked list in java
- Find start node of loop in linkedlist
- How to find nth element from end of linked list
- How to check if linked list is palindrome in java
- Add two numbers represented by linked list in java list in java
Assumption:
We do not know size of linkedlist otherwise we can directly iterate and find (length-n)th node
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 :
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
package org.arpit.java2blog; 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); } } |
Logically our linkedlist look like following:
Color node represent 3rd node from last.
Run above program, you will get following output:
|
1 2 3 4 |
5 6 7 1 2 3th node from end is : 7 |
Please go through java interview programs for more such programs.
Was this post helpful?
Let us know if this post was helpful. Feedbacks are monitored on daily basis. Please do provide feedback as that\'s the only way to improve.
