Delete nodes in linked list and binary tree

You are asked to solve two short coding tasks. You may assume standard node definitions:

• Singly linked list node: val, next
• Binary tree node: val, left, right

Task A — Remove the Nth node from the end of a linked list

Given the head of a singly linked list and an integer n, remove the n-th node from the end of the list and return the new head.

Requirements

• 1 <= n <= length(list)
• Aim for O(L) time where L is the list length, and O(1) extra space.

Task B — Delete a node from a binary tree and reconnect

Given the root of a binary tree (not necessarily a BST) and an integer key, delete one node whose value equals key and return the (possibly new) root.

To keep the tree structure valid after deletion, perform deletion using this rule:

1. Find the node X with value key.
2. Find the deepest, rightmost node in the tree D.
3. Replace X.val with D.val.
4. Delete node D from its parent by setting the corresponding child pointer to null.

Edge cases

• If key is not found, return the original root.
• If the tree has only one node and it matches key, return null.

Complexity target: O(N) time, O(N) space is acceptable (e.g., BFS queue), where N is the number of nodes.