Linked list find nth element from end

To find the nth node from the end of a linked list, you can use the two-pointer technique.

Example implementation in Java:

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

public class NthNodeFromLast {
    public static ListNode findNthNodeFromLast(ListNode head, int n) {
        ListNode slow = head;
        ListNode fast = head;

        // Move the fast pointer n nodes ahead of the slow pointer
        for (int i = 0; i < n; i++) {
            if (fast == null) {
                return null; 
                 // Invalid input: n is greater than the length of the list
            }
            fast = fast.next;
        }

        // Move both pointers until the fast pointer reaches the end of the list
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }

        // At this point, the slow pointer is pointing to the nth node from the end
        return slow;
    }

    public static void main(String[] args) {
        // Create a sample linked list: 1 -> 2 -> 3 -> 4 -> 5
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        int n = 2;
        ListNode nthNode = findNthNodeFromLast(head, n);
        if (nthNode != null) {
            System.out.println("The " + n + "th node from the end is: " + nthNode.val);
        } else {
            System.out.println("Invalid input: List is too short.");
        }
    }
}

In this example, the ListNode class represents a node in the linked list, and the findNthNodeFromLast method takes the head of the linked list and the value of n as input. It uses two pointers, slow and fast, initially pointing to the head of the list. The fast pointer is moved n nodes ahead of the slow pointer. Then both pointers are moved simultaneously until the fast pointer reaches the end of the list. At this point, the slow pointer is pointing to the nth node from the end of the list.

In the main method, a sample linked list is created with values 1, 2, 3, 4, and 5. The value of n is set to 2. The findNthNodeFromLast method is called to find the 2nd node from the end, and the result is printed to the console.

Output:

The 2nd node from the end is: 4

Note that in this example, we assume n is a valid input, meaning it is not greater than the length of the linked list. If n is greater than the length of the list, the method returns null.