⚡Flashcard Drill➔
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

  1. Find the node at index a - 1 (the node before the removed block) and the node at index b + 1 (the node after it).
  2. Link the first to the head of list2, then walk to the tail of list2 and link it to the second.
  3. The constraints guarantee b < list1.length - 1, so the node at b + 1 always exists -- no trailing-edge special case.
  4. 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 a instead of a - 1: you need the node before the removed block to relink from it.
  • Walking to index b instead of b + 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 a None check.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Linked List Problems