Splice a Second Linked List into the First Between Positions n and y
Company: Walmart Labs
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Onsite
You are given two singly linked lists. Splice the second list into the first: the n-th node of the first list links to the head of the second list, and the tail of the second list links to the y-th node of the first list. The nodes of the first list that lie strictly between those two positions are dropped.
The report describes the splice only as joining the second list at the n-th node and reconnecting at the y-th node; this version fixes 1-based positions and keeps both of those nodes, as stated in Rules below.
### Function Signature
```python
def splice_lists(list1: list[int], list2: list[int], n: int, y: int) -> list[int]:
```
### Rules
- Each list is given as the values of its nodes from head to tail. Positions are 1-based: position 1 is the head of `list1`.
- The result is the list obtained by following the new links from the head of `list1`: nodes 1 through `n` of `list1`, then every node of `list2` in order, then nodes `y` through the tail of `list1`.
- Nodes of `list1` at positions `n + 1` through `y - 1` are removed. When `y = n + 1`, nothing is removed and `list2` is inserted between two adjacent nodes.
- Return the node values of the result from head to tail.
### Constraints
- `2 <= len(list1) <= 10^4`
- `1 <= len(list2) <= 10^4`
- `1 <= n < y <= len(list1)`
- `-10^9 <= node value <= 10^9`; values may repeat.
### Examples
**Example 1**
```text
Input: list1 = [1, 2, 3, 4, 5, 6], list2 = [100, 200], n = 2, y = 5
Output: [1, 2, 100, 200, 5, 6]
```
Node 2 now links to 100, and 200 links to node 5. Nodes 3 and 4 are dropped.
**Example 2**
```text
Input: list1 = [7, 8], list2 = [9], n = 1, y = 2
Output: [7, 9, 8]
```
The positions are adjacent, so nothing is removed.
**Example 3**
```text
Input: list1 = [4, -1, 0, 3, 3], list2 = [5, 5, 5], n = 1, y = 5
Output: [4, 5, 5, 5, 3]
```
Positions 2 to 4 (values -1, 0 and 3) are dropped; the node at position 5, also with value 3, is kept as the new tail.
Overview: Splice one singly linked list into another: link the n-th node of the first list to the head of the second, link the second list's tail to the y-th node of the first, and drop the nodes in between. It tests careful pointer manipulation, 1-based position handling and edge cases such as adjacent positions.
Read the full Walmart Labs Software Engineer interview experience this question came from
You are given two singly linked lists, `list1` and `list2`, each represented as the values of its nodes from head to tail. Splice `list2` into `list1`: the `n`-th node of `list1` links to the head of `list2`, and the tail of `list2` links to the `y`-th node of `list1`. The nodes of `list1` that lie strictly between those two positions are dropped.
Positions are 1-based: position 1 is the head of `list1`. The result is the list obtained by following the new links from the head of `list1`:
- nodes 1 through `n` of `list1`, then
- every node of `list2` in order, then
- nodes `y` through the tail of `list1`.
Nodes of `list1` at positions `n + 1` through `y - 1` are removed; both the `n`-th and the `y`-th nodes are kept. When `y = n + 1`, nothing is removed and `list2` is inserted between two adjacent nodes.
Implement `splice_lists(list1, list2, n, y)` and return the node values of the result from head to tail.
**Example 1**
```text
Input: list1 = [1, 2, 3, 4, 5, 6], list2 = [100, 200], n = 2, y = 5
Output: [1, 2, 100, 200, 5, 6]
```
Node 2 now links to 100, and 200 links to node 5. Nodes 3 and 4 are dropped.
**Example 2**
```text
Input: list1 = [4, -1, 0, 3, 3], list2 = [5, 5, 5], n = 1, y = 5
Output: [4, 5, 5, 5, 3]
```
Positions 2 to 4 (values -1, 0 and 3) are dropped; the node at position 5, also with value 3, is kept as the new tail. Values may repeat, so what is kept is decided by position, not by value.
**Constraints**
- `2 <= len(list1) <= 10^4`
- `1 <= len(list2) <= 10^4`
- `1 <= n < y <= len(list1)`
- `-10^9 <= node value <= 10^9`; values may repeat.
Every value fits in a signed 32-bit integer (no value exceeds 2^31 - 1), so Java and C++ use `int`. The result has `n + len(list2) + (len(list1) - y + 1)` nodes.
Constraints
- 2 <= len(list1) <= 10^4
- 1 <= len(list2) <= 10^4
- 1 <= n < y <= len(list1)
- -10^9 <= node value <= 10^9; values may repeat.
Examples
Input: ([1, 2, 3, 4, 5, 6], [100, 200], 2, 5)
Expected Output: [1, 2, 100, 200, 5, 6]
Explanation: Source Example 1: nodes 1-2 kept, list2 inserted, nodes 3-4 dropped, nodes 5-6 kept.
Input: ([7, 8], [9], 1, 2)
Expected Output: [7, 9, 8]
Explanation: Minimum valid (source Example 2): list1 of length 2, singleton list2, n = 1, y = 2, nothing removed.
Hints
- Positions are 1-based, and both the n-th and the y-th nodes of list1 survive; only the nodes strictly between them disappear.
- Following the new links from the head of list1 passes through three consecutive pieces. Pin down where each piece starts and ends before writing any loop.
- Check your boundaries on y = n + 1, where nothing is removed, and on n = 1 with y = len(list1).