Remove Nth Node From End of List

Med

#0019Time: O(L)Space: O(1)11 companies

Patterns

Two Pointers

Data structures

Linked List

Companies

Adobe Amazon Apple Bloomberg

Prompt

Given the head of a linked list, remove the n^th node from the end of the list and return its head.

Example 1:

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Example 2:

Input: head = [1], n = 1
Output: []

Example 3:

Input: head = [1,2], n = 1
Output: [1]

Constraints:

The number of nodes in the list is sz.
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

Follow up: Could you do this in one pass?

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves two separate traversals of the linked list. The first pass is to determine the total length of the list, and the second pass is to locate and remove the desired node.

Algorithm

Create a dummy node and set its next pointer to the head of the list. This simplifies handling the edge case of removing the head node.
Traverse the list from the head to the end to calculate its total length, let's call it L.
Calculate the position of the node to be removed from the beginning. The nth node from the end is the (L - n)-th node from the start (0-indexed). We need to find the node before it.
Initialize a pointer, current, to the dummy node.
Traverse L - n steps from the dummy node. The current pointer will now be at the node just before the one we want to remove.
Update the next pointer of the current node to skip the target node: current.next = current.next.next.
Return dummy.next, which is the new head of the modified list.

Walkthrough

The core idea is to first find the length of the list, let's say L. The nth node from the end is equivalent to the (L - n + 1)-th node from the beginning. To remove this node, we need to find its predecessor, which is the (L - n)-th node from the beginning.

To handle the edge case where the head of the list needs to be removed (i.e., when n is equal to the list's length), we use a dummy node. This dummy node points to the original head, simplifying the removal logic.

After calculating the length L in the first pass, we start a second traversal from the dummy node. We iterate L - n times to reach the node just before the one we want to delete. Finally, we update the next pointer of this predecessor node to skip the target node, effectively removing it from the list.

1/**2 * Definition for singly-linked list.3 * public class ListNode {4 *     int val;5 *     ListNode next;6 *     ListNode() {}7 *     ListNode(int val) { this.val = val; }8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }9 * }10 */11class Solution {12    public ListNode removeNthFromEnd(ListNode head, int n) {13        ListNode dummy = new ListNode(0, head);14        int length = 0;15        ListNode first = head;16        while (first != null) {17            length++;18            first = first.next;19        }20 21        length -= n;22        first = dummy;23        while (length > 0) {24            length--;25            first = first.next;26        }27        first.next = first.next.next;28        return dummy.next;29    }30}

Complexity

Time

O(L)

Space

O(1)

Trade-offs

Pros

Simple to understand and implement.
The logic is straightforward and follows a clear two-step process.

Cons

Inefficient compared to a single-pass solution as it requires traversing the list twice.

This is a more optimized approach that solves the problem in a single pass. It uses two pointers, often called fast and slow, to find the nth node from the end without first needing to calculate the list's length.

Algorithm

Create a dummy node that points to the head of the list. This helps in handling edge cases like removing the first node.
Initialize two pointers, slow and fast, both pointing to the dummy node.
Move the fast pointer n + 1 steps ahead of the slow pointer. This creates a fixed gap of n nodes between them.
Now, move both slow and fast pointers one step at a time, maintaining the gap, until the fast pointer reaches the end of the list (null).
When fast is null, the slow pointer will be positioned at the node just before the nth node from the end.
Update slow.next to slow.next.next to bypass and remove the target node.
Return dummy.next, which is the head of the modified list.

Walkthrough

The strategy is to maintain a fixed-size gap of n nodes between a fast and a slow pointer. We start by creating a dummy node pointing to the head to simplify edge cases. Both fast and slow pointers are initialized to this dummy node.

First, we advance the fast pointer n + 1 steps into the list. This creates the necessary gap. After establishing the gap, we move both fast and slow pointers forward one step at a time. We continue this until the fast pointer reaches the end of the list (null).

Because of the initial gap, when fast reaches the end, the slow pointer will be positioned exactly at the node before the nth node from the end. We can then easily remove the target node by updating slow.next to point to slow.next.next. This method cleverly uses the relative distance between two pointers to find the target node in a single traversal.

1/**2 * Definition for singly-linked list.3 * public class ListNode {4 *     int val;5 *     ListNode next;6 *     ListNode() {}7 *     ListNode(int val) { this.val = val; }8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }9 * }10 */11class Solution {12    public ListNode removeNthFromEnd(ListNode head, int n) {13        ListNode dummy = new ListNode(0, head);14        ListNode slow = dummy;15        ListNode fast = dummy;16 17        // Move fast pointer n + 1 steps ahead18        for (int i = 0; i <= n; i++) {19            fast = fast.next;20        }21 22        // Move both pointers until fast reaches the end23        while (fast != null) {24            slow = slow.next;25            fast = fast.next;26        }27 28        // Remove the nth node from the end29        slow.next = slow.next.next;30 31        return dummy.next;32    }33}

Complexity

Time

O(L)

Space

O(1)

Trade-offs

Pros

Highly efficient as it solves the problem in a single pass over the list.
Constant space complexity.
An elegant and common pattern for solving linked list problems involving relative positions.

Cons

The logic can be slightly less intuitive to grasp initially compared to the two-pass method.

Solutions

Solution

1/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int val=0, ListNode next=null) { * this.val = val; * this.next = next; * } * } */ public 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 ; } }

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 ; } }

1/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @param {number} n * @return {ListNode} */ var removeNthFromEnd = function ( head , n ) { const dummy = new ListNode ( 0 , head ); let fast = dummy , slow = dummy ; while ( n -- ) { fast = fast . next ; } while ( fast . next ) { slow = slow . next ; fast = fast . next ; } slow . next = slow . next . next ; return dummy . next ; };

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

1# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution : def removeNthFromEnd ( self , head : Optional [ ListNode ], n : int ) -> Optional [ ListNode ]: dummy = ListNode ( next = head ) fast = slow = dummy for _ in range ( n ): fast = fast . next while fast . next : slow , fast = slow . next , fast . next slow . next = slow . next . next return dummy . next

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem