Return the Nth Node From the End

Given the head of a singly linked list and a number n, return the value of the nth node from the end. n = 1 means the last node. Return an empty OptionalInt if the list has fewer than n nodes (or if n is 0). OptionalInt is a container that holds either one int or nothing.

Example 1

Text

Input:  22 -> 18 -> 60 -> 78 -> 47 -> 39 -> 99, n = 3
Output: 47

graph LR
    A["22"] --> B["18"] --> C["60"] --> D["78"] --> E["47 (3rd from end)"] --> F["39"] --> G["99"]
    style E stroke-width:3px

Example 2

Text

Input:  same list, n = 7   Output: 22   (the head)
Input:  same list, n = 8   Output: empty (list too short)

Brute force: count, then walk

With len nodes, the nth node from the end is the (len - n)th node from the start, counting from 0. For example 1: len = 7, n = 3, so it's index 4, which holds 47.

A list node here is an object with a mutable next field, and null marks the end of the list.

Java

import java.util.OptionalInt;

public class Main {
    static class ListNode {
        int val;
        ListNode next;

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

    static OptionalInt nthFromEnd(ListNode head, int n) {
        int len = 0;
        for (ListNode node = head; node != null; node = node.next) len++;
        if (n <= 0 || n > len) return OptionalInt.empty();
        ListNode cur = head;
        for (int i = 0; i < len - n; i++) cur = cur.next;
        return OptionalInt.of(cur.val);
    }

    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

    static String show(ListNode list) {
        StringBuilder sb = new StringBuilder("[");
        for (ListNode n = list; n != null; n = n.next) {
            if (n != list) sb.append(", ");
            sb.append(n.val);
        }
        return sb.append("]").toString();
    }

    public static void main(String[] args) {
        ListNode list = fromArray(22, 18, 60, 78, 47, 39, 99);
        System.out.println(nthFromEnd(list, 3) + " " + nthFromEnd(list, 7) + " " + nthFromEnd(list, 8));
    }
}

Output

OptionalInt[47] OptionalInt[22] OptionalInt.empty

Time: O(len) with two passes. Space: O(1).

Optimal: two pointers n nodes apart

Move a lead pointer n nodes ahead. Then move lead and trail forward together, one node at a time. The gap between them stays n, so when lead falls off the end, trail is n nodes from the end.

Walkthrough with n = 3:

phase	lead	trail
after moving lead 3 nodes	78	22
together, step 1	47	18
together, step 2	39	60
together, step 3	99	78
together, step 4	null	47

Java

import java.util.OptionalInt;

public class Main {
    static class ListNode {
        int val;
        ListNode next;

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

    static OptionalInt nthFromEnd(ListNode head, int n) {
        if (n <= 0) return OptionalInt.empty();
        ListNode lead = head;
        for (int i = 0; i < n; i++) {
            if (lead == null) return OptionalInt.empty(); // the list is too short
            lead = lead.next;
        }
        ListNode trail = head;
        while (lead != null) {
            lead = lead.next;
            trail = trail.next;
        }
        return OptionalInt.of(trail.val);
    }

    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

    static String show(ListNode list) {
        StringBuilder sb = new StringBuilder("[");
        for (ListNode n = list; n != null; n = n.next) {
            if (n != list) sb.append(", ");
            sb.append(n.val);
        }
        return sb.append("]").toString();
    }

    public static void main(String[] args) {
        ListNode list = fromArray(22, 18, 60, 78, 47, 39, 99);
        System.out.println(nthFromEnd(list, 3) + " " + nthFromEnd(list, 7) + " " + nthFromEnd(list, 8));
    }
}

Output

OptionalInt[47] OptionalInt[22] OptionalInt.empty

Time: O(len) in one pass. Space: O(1).

Both pointers are ordinary references into the same list, so they can walk it at the same time. When n == len, lead becomes null after exactly n moves and the check inside the first loop is not triggered, so the answer is the head. When n > len, lead is null before n moves are done and the method returns early.

Follow-up: remove the nth node from the end (LeetCode 19)

LeetCode 19 asks you to delete that node. To unlink a node, the pointer must stop on the node before it.

A dummy node placed in front of the head makes this work for every position. Without it, removing the head would need a special case, because the head has no node before it.

Move lead n nodes ahead of the dummy.
Move lead and trail together until lead.next is null. Now trail is the node before the target.
Set trail.next = trail.next.next.

Java

public class Main {
    static class ListNode {
        int val;
        ListNode next;

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

    static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode lead = dummy;
        ListNode trail = dummy;
        for (int i = 0; i < n; i++) lead = lead.next;
        while (lead.next != null) {
            lead = lead.next;
            trail = trail.next;
        }
        trail.next = trail.next.next; // skip the target
        return dummy.next;
    }

    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

    static String show(ListNode list) {
        StringBuilder sb = new StringBuilder("[");
        for (ListNode n = list; n != null; n = n.next) {
            if (n != list) sb.append(", ");
            sb.append(n.val);
        }
        return sb.append("]").toString();
    }

    public static void main(String[] args) {
        System.out.println(show(removeNthFromEnd(fromArray(1, 2, 3, 4, 5), 2)));
        System.out.println(show(removeNthFromEnd(fromArray(1, 2), 2)));
        System.out.println(show(removeNthFromEnd(fromArray(1), 1)));
    }
}

Output

[1, 2, 3, 5]
[2]
[]

Time: O(len) in one pass. Space: O(1).

When n == len, trail stays on the dummy and the head is removed with no special case. LeetCode guarantees 1 <= n <= len, so lead never becomes null inside the first loop.

Edge cases

n = 0 or n > len: empty OptionalInt.
n = len: the head.
n = 1: the last node.