LeetCode 1669 - Merge In Between Linked Lists

Difficulty: 🟡 Medium
Topics: Linked List

Solution

Problem Understanding

The problem asks us to merge two singly linked lists in a very specific way. We are given list1 and list2, with sizes n and m respectively, along with two indices a and b. The task is to remove nodes from list1 starting at index a up to index b (inclusive) and insert the entire list2 in their place. The resulting list should preserve all nodes before a from list1, include all nodes from list2, and then continue with the nodes from list1 after b.

In simpler terms, list2 replaces a contiguous segment of list1 defined by the indices [a, b]. The problem guarantees valid indices and non-empty lists, so we do not need to handle empty list1 or list2. Indices are 0-based, and 1 <= a <= b < list1.length - 1 ensures the removed segment is not at the extreme ends of the list, which simplifies pointer manipulation.

Important edge cases to consider include merging at the start or end of list1, having list2 of length 1, and having consecutive nodes removed from list1 that are directly adjacent to a and b. The problem ensures the list lengths are up to 10,000, so an efficient linear-time algorithm is necessary.

Approaches

The brute-force approach would traverse list1 and list2, converting them into arrays or slices, perform the removal and insertion at the array level, and then reconstruct a new linked list. This works but requires O(n + m) extra space and is unnecessary since linked lists allow direct pointer manipulation.

The optimal approach leverages the fact that linked lists can be spliced by adjusting pointers. We traverse list1 to find the node just before a (prev_a) and the node just after b (after_b). Then we connect prev_a.next to the head of list2 and connect the tail of list2 to after_b. This approach runs in linear time relative to the lengths of list1 and list2, using O(1) extra space.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n + m)	O(n + m)	Convert lists to arrays, manipulate arrays, reconstruct list
Optimal	O(n + m)	O(1)	Traverse pointers, splice lists directly, minimal extra memory

Algorithm Walkthrough

Initialize two pointers: prev_a to None and current to list1. Traverse list1 until reaching the ath node, updating prev_a to point to the node before a. This identifies where the splice will begin.
Continue traversing list1 from node a until reaching node b. Keep a pointer after_b to the node following b. This identifies the end of the removed segment.
Traverse list2 to find its tail node. This is necessary to connect the end of list2 to the remaining segment of list1.
Connect prev_a.next to the head of list2. This attaches the replacement segment.
Connect the tail of list2 to after_b. This reconnects the remainder of list1 after the removed nodes.
Return list1 as the head of the modified linked list.

Why it works: The algorithm works because it maintains the invariant that all nodes before a and after b remain unchanged, while nodes between a and b are replaced with list2. Pointer manipulation ensures no nodes are lost, and traversal ensures all pointers are correctly updated.

Python Solution

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:
        prev_a = None
        current = list1
        index = 0
        
        # Step 1: Find node before 'a' (prev_a)
        while index < a:
            prev_a = current
            current = current.next
            index += 1
        
        # Step 2: Find node after 'b' (after_b)
        after_b = current
        while index <= b:
            after_b = after_b.next
            index += 1
        
        # Step 3: Find tail of list2
        tail_list2 = list2
        while tail_list2.next:
            tail_list2 = tail_list2.next
        
        # Step 4: Connect prev_a to head of list2
        prev_a.next = list2
        
        # Step 5: Connect tail of list2 to after_b
        tail_list2.next = after_b
        
        return list1

This implementation first locates the nodes surrounding the segment to remove, then traverses list2 to its end. The key pointer connections are straightforward: prev_a.next attaches list2, and the tail of list2 connects back to after_b. The rest of list1 remains untouched.

Go Solution

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeInBetween(list1 *ListNode, a int, b int, list2 *ListNode) *ListNode {
    var prevA *ListNode
    current := list1
    index := 0

    // Step 1: Find node before 'a' (prevA)
    for index < a {
        prevA = current
        current = current.Next
        index++
    }

    // Step 2: Find node after 'b' (afterB)
    afterB := current
    for index <= b {
        afterB = afterB.Next
        index++
    }

    // Step 3: Find tail of list2
    tailList2 := list2
    for tailList2.Next != nil {
        tailList2 = tailList2.Next
    }

    // Step 4: Connect prevA to head of list2
    prevA.Next = list2

    // Step 5: Connect tail of list2 to afterB
    tailList2.Next = afterB

    return list1
}

In Go, handling nil pointers is crucial, but otherwise the logic mirrors Python. Pointers are updated directly without needing extra data structures, preserving O(1) space complexity.

Worked Examples

Example 1: list1 = [10,1,13,6,9,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]

Step	prev_a	after_b	tail_list2	list1 state
Initial	None	None	[1000000,...]	[10,1,13,6,9,5]
Locate prev_a	Node 13	None	[1000000,...]	unchanged
Locate after_b	Node 13	Node 5	[1000000,...]	unchanged
Attach list2	Node 13	Node 5	Node 1000002	[10,1,13,1000000,1000001,1000002,5]

Example 2: list1 = [0,1,2,3,4,5,6], a = 2, b = 5, list2 = [1000000,1000001,1000002,1000003,1000004]

Step	prev_a	after_b	tail_list2	list1 state
Initial	None	None	[1000000,...]	[0,1,2,3,4,5,6]
Locate prev_a	Node 1	None	[1000000,...]	unchanged
Locate after_b	Node 1	Node 6	[1000000,...]	unchanged
Attach list2	Node 1	Node 6	Node 1000004	[0,1,1000000,1000001,1000002,1000003,1000004,6]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + m)	Traversing list1 up to index b and traversing list2 to find its tail
Space	O(1)	Only a few pointers are used, no extra data structures

This is optimal for linked list splicing. The algorithm performs a single traversal of each list and does not allocate new nodes.

Test Cases

# Provided examples
assert Solution().mergeInBetween(ListNode.from_list([10,1,13,6,9,5]), 3, 4, ListNode.from_list([1000000,1000001,1000002])).to_list() == [10,1,13,1000000,1000001,1000002,5]
assert Solution().mergeInBetween(ListNode.from_list([0,1,2,3,4,5,6]), 2, 5, ListNode.from_list([1000000,1000001,100000