19. Remove Nth Node From End of List
## description
## 19. Remove Nth Node From End of List
Given the head of a linked list, remove the nth node from the end of the list and return its head.
Example 1:
1Input: head = [1,2,3,4,5], n = 2
2Output: [1,2,3,5]Example 2:
1Input: head = [1], n = 1
2Output: []Example 3:
1Input: head = [1,2], n = 1
2Output: [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?
## notes
### Intuition
By maintaining a gap of n nodes between two pointers, when the right pointer reaches the end, the left pointer will be just before the node to remove.
### Implementation
First, advance the right pointer n steps ahead. Create a dummy node pointing to the head to handle edge cases cleanly, and set the left pointer to the dummy. Move both pointers together until right reaches null. Now left is positioned just before the target node—skip over it by setting left.next = left.next.next.
### Edge-cases
The dummy node handles removing the first node (when n equals the list length). Without it, we'd need special case logic for updating the head.
- –Time: O(n) — single pass through the list
- –Space: O(1) — only using pointers
### Complexity
## solution
1from typing import Optional
2from lcutils import ListNode
3
4# Definition for singly-linked list.
5# class ListNode:
6# def __init__(self, val=0, next=None):
7# self.val = val
8# self.next = next
9class Solution:
10 def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
11 right = head
12 while n > 0:
13 right = right.next if right else None
14 n -= 1
15
16 dummy = ListNode()
17 dummy.next = head
18 left = dummy
19 while left and right:
20 left = left.next
21 right = right.next
22
23 if left and left.next:
24 left.next = left.next.next
25 return dummy.next
26
27
28
29
30if __name__ == "__main__":
31 # Include one-off tests here or debugging logic that can be run by running this file
32 # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
33 solution = Solution()
34