This article provides a complete breakdown of the solution to LeetCode 19 Remove Nth Node From End of List: from the problem-solving approach and algorithm steps to time and space complexity, and it also summarizes boundary cases and compares three solutions, helping you understand Remove Nth Node From End of List from scratch.
Explore diverse LeetCode solutions in Python, C++, JavaScript, SQL, and TypeScript. Ideal for interview prep, learning, and code practice in multiple programming languages. Github Repo Link
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 <= 300 <= Node.val <= 1001 <= n <= sz
Follow up: Could you do this in one pass?
Table of contents
TogglePython
# time complexity: O(n) # space complexity: O(1) from typing import Optional 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]: total = 0 countNode = resNode = head while countNode: total += 1 countNode = countNode.next delIdx = total - n - 1 if delIdx < 0: head = head.next return head currentIdx = 0 while resNode: if currentIdx == delIdx: if resNode.next.next: resNode.next = resNode.next.next else: resNode.next = None return head else : resNode = resNode.next currentIdx += 1 return head root = ListNode(1) root.next = ListNode(2) root.next.next = ListNode(3) root.next.next.next = ListNode(4) root. next.next.next.next = ListNode(5) print(Solution().removeNthFromEnd(root, 2))
LeetCode Problem Extension Exercises
Other problem-solving notes in the same series are recommended for practice:
Solution to Remove Nth Node From End of List
A one-way sequence cannot be read backwards, but the nth node from the end can be located using a fixed distance between fast and slow pointers: let the fast pointer move n+1 steps first, then both pointers move forward synchronously. When the fast pointer reaches the end, the slow pointer will stop exactly before the node to be deleted. Combined with dummy nodes, even the special case of "deleting the head node" can be eliminated.
Algorithm steps for removing the Nth Node from the End of the List
- Create a dummy node pointing to the head, and both the fast and slow nodes point to the dummy node.
- Let fast move forward n+1 steps first.
- fast and slow proceed in tandem until fast becomes null.
- At this point, slow.next is the node to be deleted. Execute slow.next = slow.next.next, and postback dummy.next.
Complexity analysis of removing the Nth Node from the end of the list.
| project | Complexity |
|---|---|
| Time complexity | O(L) |
| Space complexity | O(1) |
The two pointers traverse the sequence once in a total of O(L) time, requiring only one scan. With only a few index variables, the space complexity is O(1) – which is better than the two-pass solution of "calculating the length first and then traversing once".
Boundary cases and common errors of "Remove Nth Node From End of List"
- Using dummy nodes eliminates the need for the special case where "the head node is being deleted".
- Faster methods require taking n+1 steps instead of n steps; otherwise, the wrong node will be deleted.
- The problem guarantees that n is valid; otherwise, it checks whether fast has become null beforehand.
- If the original node needs to be released after deletion, the manual handling depends on the language.
Comparison of other solutions for removing the Nth Node from the End of the List
| solution | time | space | illustrate |
|---|---|---|---|
| Walk it once to calculate the length, then walk it a second time. | O(L) | O(1) | It requires two trips; the logic is quite intuitive. |
| After storing all nodes in the array, locate them. | O(L) | O(L) | Spend more space |
| Fast and slow pointers can be adjusted in one go. | O(L) | O(1) | This article adopts |

