Replace a Range of Nodes in a Linked List with Another Linked List

You are given two singly linked lists, `list1` and `list2`, and two indices `i` and `j`. Replace the nodes of `list1` numbered `i` through `j` (inclusive) with the whole of `list2`, and return the head of the resulting list. ### Function Signature ```python def replace_range(list1: ListNode, list2: Optional[ListNode], i: int, j: int) -> Optional[ListNode]: ``` ### Rules - `ListNode` is a singly linked list node with an integer field `val` and a field `next` that is `None` at the tail. - Nodes of `list1` are numbered from `0` at the head. Nodes `i`, `i + 1`, ..., `j` are removed. - All nodes of `list2` are inserted, in their original order, where the removed nodes were: node `i - 1` of `list1` (if it exists) is followed by the first node of `list2`, and the last node of `list2` is followed by node `j + 1` of `list1` (if it exists). - `list2` may be empty (`None`); then nodes `i` through `j` are simply deleted. - When `i = 0`, the result starts with the first node of `list2`, or with node `j + 1` of `list1` if `list2` is empty. - Return the head of the result, or `None` if the result has no nodes (possible only when `list2` is empty, `i = 0` and `j = n - 1`). - You may relink the existing nodes of both lists. The result is checked by its sequence of values from head to tail, so the answer is unique. - In the examples a linked list is written as the array of its values from head to tail, and `[]` stands for `None`. ### Constraints - `1 <= n <= 10^4`, where `n` is the number of nodes in `list1` - `0 <= m <= 10^4`, where `m` is the number of nodes in `list2` - `0 <= i <= j < n` - `-10^9 <= val <= 10^9` for every node of both lists ### Examples **Example 1** ```text Input: list1 = [5, 8, 2, 7, 4], list2 = [11, 12], i = 1, j = 3 Output: [5, 11, 12, 4] ``` Nodes 1 through 3 of `list1` (values 8, 2 and 7) are replaced by the two nodes of `list2`. **Example 2** ```text Input: list1 = [1, 2, 3], list2 = [9, 9], i = 0, j = 0 Output: [9, 9, 2, 3] ``` The head of `list1` is replaced, so the result starts with the first node of `list2`. **Example 3** ```text Input: list1 = [1, 2, 3, 4], list2 = [], i = 2, j = 3 Output: [1, 2] ``` `list2` is empty, so nodes 2 and 3 are deleted and node 1 becomes the tail.