Find nth Node from End of Linked List – Java Program

This Java program demonstrates how to find the nth node from the end of a linked list. The program includes the implementation of the linked list nodes and the logic to find the desired node.

Program Structure

The program is structured into three main components:

1. ListNode Class: Defines the node structure for the linked list.
2. FindNthFromEnd Class: Contains the method to find the nth node from the end of the linked list.
3. Main Class: Contains the main method to execute the program and test the finding functionality.

Java Code

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */

    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public class FindNthFromEnd {
        /**
         * Finds the nth node from the end of a linked list.
         * 
         * @param head The head of the linked list.
         * @param n The position from the end (1-based index).
         * @return The nth node from the end of the linked list.
         */
        public ListNode findNthFromEnd(ListNode head, int n) {
            ListNode firstPointer = head;
            ListNode secondPointer = head;
            
            // Move the first pointer n steps ahead
            for (int i = 0; i < n; i++) {
                if (firstPointer == null) return null; // If n is greater than the length of the list
                firstPointer = firstPointer.next;
            }
            
            // Move both pointers until the first pointer reaches the end
            while (firstPointer != null) {
                firstPointer = firstPointer.next;
                secondPointer = secondPointer.next;
            }
            
            // The second pointer is now at the nth node from the end
            return secondPointer;
        }
    }

    public class Main {
        public static void main(String[] args) {
            // Create a linked list for testing
            ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
            
            // Find the 2nd node from the end
            FindNthFromEnd finder = new FindNthFromEnd();
            ListNode nthNode = finder.findNthFromEnd(head, 2);
            
            // Print the value of the nth node from the end
            if (nthNode != null) {
                System.out.println("The nth node from the end has value: " + nthNode.val);
            } else {
                System.out.println("The list is shorter than the provided value of n.");
            }
        }
    }
    

Explanation

ListNode Class: This class represents a node in the linked list. Each node contains an integer value and a reference to the next node.

FindNthFromEnd Class: This class contains the method findNthFromEnd that finds the nth node from the end of the linked list. It uses the two-pointer technique to efficiently locate the desired node.

Main Class: This class is used for testing the functionality. It creates a sample linked list, finds the 2nd node from the end using the FindNthFromEnd class, and prints the result.