This problem requires you to remove the nth node from the end of a singly linked list. Using a two-pointer approach, you can efficiently solve it by maintaining one pointer delayed by n steps behind the other, then adjusting pointers to remove the target node.
Problem Statement
You are given the head of a singly linked list, and an integer n. Your task is to remove the nth node from the end of the list and return its head.
For example, given a list head = [1,2,3,4,5] and n = 2, after removing the second node from the end, the list should become [1,2,3,5].
Examples
Example 1
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
Example details omitted.
Example 2
Input: head = [1], n = 1
Output: []
Example details omitted.
Example 3
Input: head = [1,2], n = 1
Output: [1]
Example details omitted.
Constraints
- The number of nodes in the list is sz.
- 1 <= sz <= 30
- 0 <= Node.val <= 100
- 1 <= n <= sz
Solution Approach
Two Pointer Approach
Start by placing two pointers on the head of the list. Move one pointer n steps forward. Then move both pointers one step at a time until the first pointer reaches the end. The second pointer will then be just before the node to be removed.
Edge Case Handling
Handle edge cases such as when the list contains only one element, or when n equals the size of the list. In these cases, you need to remove the first node or handle list emptying properly.
Update List Pointers
When the second pointer reaches the node just before the one to be removed, update its next pointer to skip the node. This efficiently removes the target node from the list.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
The time complexity is O(sz) because we traverse the list at most twice, where sz is the number of nodes in the list. The space complexity is O(1) as we only use two pointers, irrespective of the list size.
What Interviewers Usually Probe
- Look for knowledge of linked-list pointer manipulation.
- Assess the candidate's understanding of two-pointer techniques.
- Evaluate their handling of edge cases, such as small lists or when n is at list boundaries.
Common Pitfalls or Variants
Common pitfalls
- Not properly handling the edge case where the list has only one element or when n is equal to the list length.
- Failing to correctly update the next pointer of the node before the one to be removed.
- Misunderstanding the two-pointer technique and trying to manipulate the list in a less efficient way.
Follow-up variants
- What if the list is cyclic? How would you handle that scenario?
- Remove the nth node from the beginning or middle of the list instead of the end.
- Modify the list such that it supports dynamic removals, rather than a fixed one-time operation.
How GhostInterview Helps
- GhostInterview provides a step-by-step walkthrough for the two-pointer technique used to solve this problem.
- It offers real-time feedback on your approach, ensuring you're correctly implementing the two-pointer strategy and edge case handling.
- Through practice questions, GhostInterview helps reinforce your ability to manage linked-list pointer manipulation in time-sensitive interview scenarios.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
How do I remove the nth node from the end of a linked list?
You can solve this by using the two-pointer technique, where one pointer is moved n steps ahead, and both pointers move together until the first pointer reaches the end.
What is the time complexity of removing the nth node from the end of the list?
The time complexity is O(sz), where sz is the number of nodes in the list, as we traverse the list at most twice.
Can I solve this problem using a single pass through the list?
Yes, using the two-pointer technique, you can solve the problem in a single pass, making it efficient.
What edge cases should I consider for this problem?
Edge cases include handling an empty list, a list with one element, and when n is equal to the length of the list.
How does the two-pointer approach work for this problem?
The two-pointer approach involves moving one pointer n steps ahead of the other. Then, both pointers move together until the first pointer reaches the end, at which point the second pointer will point to the node just before the one to be removed.
Need direct help with Remove Nth Node From End of List instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Remove Nth Node From End of List from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Rotate a singly linked list to the right by k positions using careful pointer manipulation and two-pointer traversal techniques.
Open problem page#82 Remove Duplicates from Sorted List IIRemove duplicates from a sorted linked list, leaving only distinct values, and return the modified list in sorted order.
Open problem page#86 Partition ListPartition a linked list such that all nodes less than x come before nodes greater than or equal to x while preserving relative order.
Open problem page