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.
