Program for nth node from the end of a Linked List

The problem, simply

You get a linked list: a chain of boxes, each with a number and an arrow to the next box. You also get a number n.

Give back the box that is n places from the end. With n = 1 that is the last box, with n = 2 the one before it, and so on. If the chain is shorter than n, there is no such box, so give back null.

The catch: you can only walk forward from the head. You do not know how long the chain is until you reach the end.

A story to remember it

Picture it

Examples

Way 1: the simple way

Count first, then walk.

1. Walk the whole chain and count the boxes. Call the count len.
2. If n is bigger than len, give back null.
3. The box n from the end is the box at position len - n from the start (counting from 0). Walk that many steps from the head.

class Solution {
    public ListNode nthFromEnd(ListNode head, int n) {
        int len = 0;
        for (ListNode cur = head; cur != null; cur = cur.next) len++;  // count the boxes
        if (n <= 0 || n > len) return null;                            // no such box
        ListNode cur = head;
        for (int i = 0; i < len - n; i++) cur = cur.next;               // walk len - n steps
        return cur;
    }
}

How long it takes: one walk to count and part of a second walk, so O(n) where n here means the number of boxes. Extra room: one counter and one finger, O(1). This is already fine, but it reads the chain twice, and interviewers usually ask for one walk.

Way 2: the clever way

Use the broom. Two fingers, fast and slow, both start at the head.

1. Move fast forward n steps. If it falls off the chain before finishing, the chain is too short, so give back null.
2. Now fast is n boxes ahead of slow. Move both one step at a time.
3. When fast steps off the end (it becomes null), slow is exactly n boxes from the end. Give back slow.

class Solution {
    public ListNode nthFromEnd(ListNode head, int n) {
        if (n <= 0) return null;
        ListNode fast = head, slow = head;
        for (int i = 0; i < n; i++) {        // give fast a head start of n steps
            if (fast == null) return null;   // the chain is shorter than n
            fast = fast.next;
        }
        while (fast != null) {               // walk together until fast falls off
            fast = fast.next;
            slow = slow.next;
        }
        return slow;                         // n boxes from the end
    }
}

How long it takes: fast walks the chain once and slow walks part of it, so O(n). Extra room: two fingers, O(1). The big win is one single walk, which matters when the chain is a stream you can read only once.

Watch out for

• n bigger than the length: check for null during the head start, not after.
• n equal to the length: fast becomes null right after the head start and the answer is the head. Make sure the code does not treat this as "too big".
• An empty chain: head is null, the head start loop returns null at once.
• n of 0 or below: there is no 0th box from the end. Return null.

What interviewers ask next

• Delete the nth box from the end (LeetCode 19). Put a fake box in front of the head, called a dummy. Run the same broom from the dummy with a gap of n + 1, so slow stops on the box before the one to delete. Then do slow.next = slow.next.next. The dummy makes deleting the head easy.
• Find the middle box. Use two fingers again, but fast moves 2 steps for every 1 step of slow.
• Can you do it with recursion? Yes. Go all the way down, then count up on the way back. When the count hits n, that box is the answer. It uses O(n) stack room though.
• What if the list is a stream and you may keep only n values? Keep the last n values in a ring of size n. When the stream ends, the oldest value in the ring is the answer.

Remember this

Grown-up words: the boxes are nodes, the broom is a fixed gap between two pointers (the two pointer or runner technique), and the fake front box is a dummy node.