Find nth element from end of linked list

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:

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 :

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:

5 6 7 1 2
3th node from end is : 7