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

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

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

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

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.