Remove Nth Node from End of List
Examples
Example 1:
Input: head = [1,2,3,4], n = 2
Output: [1,2,4]
Example 2:
Input: head = [5], n = 1
Output: []
Example 3:
Input: head = [1,2], n = 2
Output: [2]
Example 1:
Input: head = [1,2,3,4], n = 2
Output: [1,2,4]
Example 2:
Input: head = [5], n = 1
Output: []
Example 3:
Input: head = [1,2], n = 2
Output: [2]
You are given the beginning of a linked list head, and an integer n.
Remove the nth node from the end of the list and return the beginning of the list.
sz.1 <= sz <= 300 <= Node.val <= 1001 <= n <= szUse a dummy node before the head and keep a gap of n nodes between two pointers. Advance fast n + 1 steps from the dummy, then move fast and slow together until fast hits the end. slow will be right before the node to remove, so you can bypass it. This cleanly handles edge cases like removing the head (e.g. a single-node list).
Maintaining a fixed gap ensures that when fast reaches the end, slow is positioned immediately before the nth node from the end. Removing slow.next therefore deletes exactly the target node in one pass.
O(n)O(1)class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy = ListNode(0, head)
fast = dummy
for _ in range(n + 1):
fast = fast.next
slow = dummy
while fast:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return dummy.next