Remove Node From End of Linked List

NeetCode: Remove Node From End of Linked List · LeetCode: 19. Remove Node From End of Linked List · Difficulty: Medium

Given the head of a linked list and an integer n, remove the n-th node from the end and return the head. n is always valid.

Example

Text

Input:  1 -> 2 -> 3 -> 4, n = 2    Output: 1 -> 2 -> 4
Input:  5, n = 1                   Output: (empty)

Java linked structures use null and mutable fields, so the list is a chain of ListNode objects, the end is next == null, and the empty list is null. The helper fromArray builds a list from its values and toList copies a list into an ArrayList for printing.

Brute force: go through an ArrayList

Java

import java.util.ArrayList;
import java.util.List;

class ListNode {
    int val;
    ListNode next;

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

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        List<Integer> values = new ArrayList<>();
        for (ListNode cur = head; cur != null; cur = cur.next) {
            values.add(cur.val);
        }
        values.remove(values.size() - n); // int argument: removes by index
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        for (int v : values) {
            tail.next = new ListNode(v);
            tail = tail.next;
        }
        return dummy.next;
    }
}

public class Main {
    static ListNode fromArray(int... values) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        for (int v : values) {
            tail.next = new ListNode(v);
            tail = tail.next;
        }
        return dummy.next;
    }

    static List<Integer> toList(ListNode head) {
        List<Integer> out = new ArrayList<>();
        for (ListNode cur = head; cur != null; cur = cur.next) {
            out.add(cur.val);
        }
        return out;
    }

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

Output

[1, 2, 4]
[]

values.remove(values.size() - n) calls remove(int index) because the argument is an int.

Time: O(n). Space: O(n).

Optimal: count, then walk to the node before the target

The node to remove is at index len - n from the front. Pass 1 counts the nodes. Pass 2 walks prev to the node just before the target, which is len - n steps from a dummy node placed in front of the head. Setting prev.next = prev.next.next unlinks the target. The dummy node means deleting the head is the same code as deleting any other node.

Example 1 -> 2 -> 3 -> 4, n = 2: len = 4, so step len - n = 2 times. prev starts at the dummy, moves to node 1, then node 2. Its next is node 3, the target. Replace that link with 3.next, giving 1 -> 2 -> 4.

Java

import java.util.ArrayList;
import java.util.List;

class ListNode {
    int val;
    ListNode next;

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

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // pass 1: count
        int len = 0;
        for (ListNode p = head; p != null; p = p.next) {
            len++;
        }

        // pass 2: move prev to the node before the target
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        for (int i = 0; i < len - n; i++) {
            prev = prev.next;
        }
        prev.next = prev.next.next; // splice the target out
        return dummy.next;
    }
}

public class Main {
    static ListNode fromArray(int... values) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        for (int v : values) {
            tail.next = new ListNode(v);
            tail = tail.next;
        }
        return dummy.next;
    }

    static List<Integer> toList(ListNode head) {
        List<Integer> out = new ArrayList<>();
        for (ListNode cur = head; cur != null; cur = cur.next) {
            out.add(cur.val);
        }
        return out;
    }

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

Output

[1, 2, 4]
[]
[2]

Time: O(n), two passes. Space: O(1).

A one-pass version keeps two pointers n nodes apart: advance fast n steps from the dummy, then move fast and slow together until fast.next is null. It is also O(n) and O(1). The two-pass count is shown because its index arithmetic is easier to check.

How to explain it in an interview

Say first: "Copy the values into a list, drop index len - n, rebuild the list: O(n) time and space."
Key insight: the n-th from the end is the (len - n)-th from the front, so counting once turns "from the end" into "from the front".
Code it in steps: (1) count the length; (2) put a dummy node before the head and start prev there; (3) advance len - n times with prev = prev.next; (4) prev.next = prev.next.next; (5) return dummy.next.
Complexity to state: O(n) time with two passes, O(1) extra space.
Likely follow-ups / pitfalls: "Do it in one pass?" Use two pointers n nodes apart. Removing the head (n == len) works with no special case because prev starts on the dummy node. Returning head instead of dummy.next returns a removed node in that case.