Program for Nth Node from the End of a Linked List

Problem Statement

Given a linked list and a positive integer n, find the nth node from the end of the linked list. If n is greater than the length of the list, return null or handle appropriately.

Example

Input: 1 -> 2 -> 3 -> 4 -> 5, n = 2
Output: 4 (2nd node from end)

Input: 7 -> 8 -> 9, n = 3
Output: 7 (3rd node from end, which is head)

Input: 1 -> 2, n = 5
Output: null (n > length of list)

Brute Force Approach (Two Pass)

Intuition

First calculate the length of the list. Then the nth node from end is the (length - n + 1)th node from the beginning.

Algorithm

Traverse the list to find its length
Calculate position from start: pos = length - n + 1
If pos <= 0, return null (n > length)
Traverse again to the pos-th node
Return that node

Code

java

class Node {
    int data;
    Node next;
    
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class NthFromEndBrute {
    public static Node nthFromEndBruteForce(Node head, int n) {
        if (head == null || n <= 0) {
            return null;
        }
        
        // First pass: Calculate length
        int length = 0;
        Node temp = head;
        while (temp != null) {
            length++;
            temp = temp.next;
        }
        
        // Check if n is valid
        if (n > length) {
            return null;
        }
        
        // Calculate position from start
        int posFromStart = length - n + 1;
        
        // Second pass: Go to that position
        temp = head;
        for (int i = 1; i < posFromStart; i++) {
            temp = temp.next;
        }
        
        return temp;
    }
    
    public static void printList(Node head) {
        while (head != null) {
            System.out.print(head.data);
            if (head.next != null) System.out.print(" -> ");
            head = head.next;
        }
        System.out.println();
    }
}

Complexity Analysis

Time Complexity: O(n) - Two passes through the list
Space Complexity: O(1) - Only using constant extra space

Optimal Approach (Two Pointers - Single Pass)

Intuition

Use two pointers with a gap of n nodes between them. Move the first pointer n steps ahead, then move both pointers together. When the first pointer reaches the end, the second pointer will be at the nth node from end.

Algorithm

Initialize two pointers fast and slow at head
Move fast n steps ahead
If fast becomes null, n equals length (return head)
If fast went past null, n > length (return null)
Move both pointers until fast reaches the last node
slow is now at the nth node from end

Code

java

class Node {
    int data;
    Node next;
    
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class NthFromEndOptimal {
    public static Node nthFromEndOptimal(Node head, int n) {
        if (head == null || n <= 0) {
            return null;
        }
        
        Node fast = head;
        Node slow = head;
        
        // Move fast n steps ahead
        for (int i = 0; i < n; i++) {
            if (fast == null) {
                // n is greater than length
                return null;
            }
            fast = fast.next;
        }
        
        // Move both until fast reaches null (past the last node)
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        
        return slow;  // slow is now at nth from end
    }
    
    public static void printList(Node head) {
        while (head != null) {
            System.out.print(head.data);
            if (head.next != null) System.out.print(" -> ");
            head = head.next;
        }
        System.out.println();
    }
    
    public static Node createList(int[] arr) {
        if (arr.length == 0) return null;
        Node head = new Node(arr[0]);
        Node curr = head;
        for (int i = 1; i < arr.length; i++) {
            curr.next = new Node(arr[i]);
            curr = curr.next;
        }
        return head;
    }
    
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        Node head = createList(arr);
        
        System.out.print("List: ");
        printList(head);
        
        for (int n = 1; n <= 6; n++) {
            Node result = nthFromEndOptimal(head, n);
            if (result != null) {
                System.out.println(n + "th from end: " + result.data);
            } else {
                System.out.println(n + "th from end: null (n > length)");
            }
        }
    }
}

Complexity Analysis

Time Complexity: O(n) - Single pass through the list
Space Complexity: O(1) - Only using constant extra space

Visual Representation

List: 1 -> 2 -> 3 -> 4 -> 5, n = 2

Initial:
fast = 1, slow = 1

After moving fast 2 steps:
fast = 3, slow = 1

After moving both until fast reaches null:
fast = null (past 5), slow = 4

Result: 4 (2nd from end)

Gap maintained:
1 -> 2 -> 3 -> 4 -> 5 -> null
          F              
S                        
|___n=2___|

Key Takeaways

Two-Pointer Technique: Maintain fixed gap between pointers
Single Pass: More efficient than calculating length first
Gap = n: When fast is at end, slow is at nth from end
Edge Cases: Handle n > length, n = 0, empty list
Dummy Node for Deletion: Simplifies deleting nth from end
Classic Interview Problem: LeetCode #19 - Remove Nth Node From End of List
Variation Awareness: Finding vs deleting nth from end
Off-by-One Careful: Understand whether to stop at the node or before it

Program for nth node from the end of a Linked List

Program for Nth Node from the End of a Linked List

Problem Statement

Example

Brute Force Approach (Two Pass)

Intuition

Algorithm

Code

Complexity Analysis

Optimal Approach (Two Pointers - Single Pass)

Intuition

Algorithm

Code

Complexity Analysis

Related Problem: Delete Nth Node from End

Visual Representation

Key Takeaways