Splice Into a List

Medium

You are given two singly linked lists, base and insert. The nodes of base are numbered from 0. Remove every node of base with an index from start to end inclusive and put the whole of insert in their place. Return the head of the resulting list. The first and the last node of base are never removed. For example, if base is 7 → 2 → 9 → 4 → 6, start = 1, end = 3 and insert is 50 → 60, the result is 7 → 50 → 60 → 6.

Example 1

base=list_node([7, 2, 9, 4, 6]), start=1, end=3, insert=list_node([50, 60]) → [7, 50, 60, 6]

Nodes 1 to 3 (2, 9, 4) are cut out and 50 and 60 take their place: [7, 50, 60, 6].

Example 2

base=list_node([1, 2, 3]), start=1, end=1, insert=list_node([8, 8, 8]) → [1, 8, 8, 8, 3]

Only the middle node 2 is removed; three 8s are inserted instead.

Example 3

base=list_node([5, 0, 0, 0, 5]), start=2, end=3, insert=list_node([1]) → [5, 0, 1, 5]

Constraints

3 ≤ length of base ≤ 10⁴
1 ≤ length of insert ≤ 10⁴
1 ≤ start ≤ end < length of base − 1

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Linked List

Similar problems

Adding Digit Lists Medium Drop the K-th Node From the Tail Medium Trade Places in Twos Medium Move the Tail to the Front Medium Sorted List, Unique Values Only Medium

Input

base=list_node([7, 2, 9, 4, 6]), start=1, end=3, insert=list_node([50, 60])

Expected

[7, 50, 60, 6]

Run checks the first 3 tests in your browser. Submit checks all 98 tests on the server, hidden ones included.