Remove Nth Node From End of List: Problem Solving Tutorial - 3 Solutions Comparison | LeetCode 19 Best Practice

Remove Nth Node From End of List: Problem Solving Tutorial Diagram | LeetCode 19

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

Medium
 

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?

				
					# 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

  1. Create a dummy node pointing to the head, and both the fast and slow nodes point to the dummy node.
  2. Let fast move forward n+1 steps first.
  3. fast and slow proceed in tandem until fast becomes null.
  4. 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.

projectComplexity
Time complexityO(L)
Space complexityO(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

solutiontimespaceillustrate
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