Find kth node from end of the linked list in JAVA

JAVA Program to find kth node from the end in A Singly Linked List

In this page of Data Structures we’ll take a look at the solution of a problem where it has been asked to find the kth node from the end of the Linked List in JAVA. Here we’ve used a rather simpler solution of finding out the index of the element by basic mathematics implementation using the length of the Linked List.

Finding the kth Node from the end in liked list

Implementation

We know that,in singly linked list traversal is done through front only. so we will count the element from front to end of the linked list.

Then we’ll find out the index of that kth node from the beginning of the list by subtracting its position, from the end, from the length of the linked list.

We can solve this problem in one traversal only. The idea is to start from the head node to move a pointer K nodes ahead  in given list.

JAVA Program to find the kth node from the end

Algorithm

  • printk(k)
  • Node temp = head
  • FOR int i=0; i++ Until temp!=0
  • temp = temp->next;
  • length++
  • temp = head
  • WHILE i = 1 to i < length – k + 1
  • temp = temp->next
  • PRINT temp->data
Program in JAVA to find Kth node from the end of a linked list

Code in JAVA Programming Language 

import java.util.*;
public class Main {
    public static void main(String[] args) throws Exception {
    LinkedList ll = new LinkedList();
    ll.addItem(70);
    ll.addItem(60);
    ll.addItem(50);
    ll.addItem(40);
    ll.addItem(30);
    ll.addItem(20);
    ll.addItem(10);
    ll.printk(4);
    }
}
class LinkedList {
    private class Node {
    int data;
    Node next;
    // Node constructor
    // There are two fields in the node- data and address of next node
        public Node(int data, Node next) {
            this.data = data;
            this.next = next;
        }
    }
    private Node head;
    private Node tail;
    private int size;
    // Linked list constructor
    public LinkedList() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }
    // Function to find the size of linked list
    public int size() {
        return this.size;
    }
    // Function to check whether linked list is empty or not
    public boolean isEmpty() {
        return this.size() == 0;
    }
    // Function to add a node in beginning of linked list
    public void addItem(int item) {
        // Create a temp node which points to head
        Node temp = new Node(item, head);
        // If linked list is empty, temp is the head and tail node both
        if (this.size == 0) {
            this.head = this.tail = temp;
        }
        // else set the head such that it now points to temp node
        else {
            this.head = temp;
        }
        this.size++;
    }
    //Function to find kth node from the END
    void printk(int k) 
    { 
        int length = 0; 
        Node temp = head; 
  
        for(int i=0;temp!=null;i++){
            temp = temp.next; 
            length++;
        }  
        temp = head; 
        
        //to get kth node from the end we can also say that we want (length-k+1) node from the beginning
        int i = 1;
        while( i < length - k + 1){
            temp = temp.next; 
            i++;
        }
        System.out.println( k + "th Node from the end is " + temp.data); 
    }

}
Output
4th Node from the end is 40