NeetCode #315LC-1669MediumLinked List
← Back to All Problems#315 · #1669 · Merge In Between Linked Lists(合并两个链表)
📌 Problem Statement & Constraints
You are given two linked lists
list1 and list2, and two integers a and b. Remove the nodes of list1 from index a to index b inclusive, and insert list2 in their place. Return the head of the resulting list. Constraints: 3 <= list1.length <= 10^4, 1 <= list2.length <= 10^4, 0 <= a <= b < list1.length - 1.💡 Core Algorithmic Approaches
- Find the node at index
a - 1(the node before the removed block) and the node at indexb + 1(the node after it). - Link the first to the head of
list2, then walk to the tail oflist2and link it to the second. - The constraints guarantee
b < list1.length - 1, so the node atb + 1always exists -- no trailing-edge special case. - This is pure pointer surgery with O(1) extra space.
💻 Benchmark Python3 Implementation
class Solution:
def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:
# node at index a-1
prev = list1
for _ in range(a - 1):
prev = prev.next
# node at index b+1
after = list1
for _ in range(b + 1):
after = after.next
# splice list2 between them
prev.next = list2
tail = list2
while tail.next:
tail = tail.next
tail.next = after
return list1⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n + m): finding the boundaries plus walking list2's tail.
💾 Space Complexity
O(1): pointer manipulation only.
⚠️ Interview Pitfalls & Follow-ups
- Walking to index
ainstead ofa - 1: you need the node before the removed block to relink from it. - Walking to index
binstead ofb + 1: you need the node after the removed block. - Forgetting to connect list2's tail: the rest of list1 would be dropped.
- Assuming
b == list1.length - 1: the constraints exclude it, but the general solution would need aNonecheck.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.