mediumLinked List Essentials

Remove Nth Node From End of List

Remove the nth node from the end of a linked list.

LeetCode ↗

Work through the cases

3 examples

Input notation

List values on line 1; valid n on line 2, counting from 1.

Expected result

Remaining values separated by spaces, or empty.

Case 1

Input

2 4 6 8
2

Expected output

2 4 8

Case 2

Input

7
1

Expected output

empty

Case 3

Input

1 2 3
3

Expected output

2 3

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

The first idea is to count the length L, then walk L-n steps and delete. sz ≤ 30 would pass, but the follow-up asks for one pass. Until we reach the end we do not know where the n-th node from the end is, and deletion still needs its predecessor. Give the fast pointer a head start of n steps, then move both; when fast hits the tail, slow sits on the predecessor. A dummy node makes deleting the head the same as deleting a middle node. So one walk with fast and slow locates and removes the node.

We define two pointers fast and slow, both initially pointing to the dummy head node of the linked list.

Next, the fast pointer moves forward n steps first, then fast and slow pointers move forward together until the fast pointer reaches the end of the linked list. At this point, the node pointed to by slow.next is the predecessor of the n-th node from the end, and we can delete it.

The time complexity is O(n), where n is the length of the linked list. The space complexity is O(1).

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode fast = dummy, slow = dummy;
        while (n-- > 0) {
            fast = fast.next;
        }
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.