7.18 Merge In Between Linked Lists

7.18.1 Problem Metadata

7.18.2 Description

You are given two linked lc-lists: lc-list1 and lc-list2 of sizes n and m respectively.

Remove lc-list1’s nodes from the a-th node to the b-th node (0-indexed), and put lc-list2 in their place.

Build the result lc-list and return its head.

7.18.3 Examples

Input: lc-list1 = [10,1,13,6,9,5], a = 3, b = 4, lc-list2 = [1000000,1000001,1000002]
Output: [10,1,13,1000000,1000001,1000002,5]
Explanation: We remove the nodes at positions 3 and 4 and put the entire lc-list2 in their place.

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

7.18.4 Constraints

  • 3 <= lc-list1.length <= 10^4
  • 1 <= a <= b < lc-list1.length - 1
  • 1 <= lc-list2.length <= 10^4

7.18.5 Solution - Pointer Manipulation

7.18.5.1 Walkthrough

The solution uses a three-phase pointer manipulation strategy: (1) locate the node before the removal range, (2) find the node after the removal range, and (3) reconnect pointers to splice in lc-list2.

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

Phase 1: Find node before position a

Initial state (with dummy):
dummy → 10 → 1 → 13 → 6 → 9 → 5 → null
^l      (index 0 after dummy)

After traversing a=3 times:
dummy → 10 → 1 → 13 → 6 → 9 → 5 → null
                  ^l
                  (l is at index 2, l.next is at index 3)

Phase 2: Find node after position b

Starting from l, traverse (b-a+1) = (4-3+1) = 2 times:
dummy → 10 → 1 → 13 → 6 → 9 → 5 → null
                  ^l        ^r
                            (r is at index 4, r.next is at index 5)

Phase 3: Find tail of lc-list2

lc-list2: 1000000 → 1000001 → 1000002 → null
                            ^lc-list2LastNode

Phase 4: Reconnect pointers

Step 1: l.next = lc-list2
dummy → 10 → 1 → 13 ┐     6 → 9 → 5 → null
                  ^l │          ^r.next
                     └→ 1000000 → 1000001 → 1000002 → null
                                              ^lc-list2LastNode

Step 2: lc-list2LastNode.next = r.next
dummy → 10 → 1 → 13 → 1000000 → 1000001 → 1000002 → 5 → null
                  ^l                       ^lc-list2LastNode  ^r.next

Final result: [10,1,13,1000000,1000001,1000002,5] ✓

This approach correctly removes nodes at indices 3-4 (values 6,9) and inserts lc-list2 in their place.

7.18.5.2 Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(1)

7.18.5.3 Implementation Steps

  1. Create dummy node: Initialize a dummy node pointing to lc-list1 to handle edge cases where removal starts at index 0.
  2. Locate node before removal range: Traverse a steps from dummy to find node l where l.next points to the first node to be removed.
  3. Locate node at end of removal range: Starting from l, traverse (b - a + 1) steps to find node r at position b.
  4. Find tail of lc-list2: Traverse lc-list2 to its last node.
  5. Reconnect pointers:
    • Set l.next = lc-list2 (connect left portion to lc-list2)
    • Set lc-list2LastNode.next = r.next (connect lc-list2 tail to right portion)
  6. Return result: Return dummyHead.next

7.18.5.4 Code - Java

class Solution {
    public ListNode mergeInBetween(ListNode lc-list1, int a, int b, ListNode lc-list2) {
        // create a dummy node -- 
        //   If we are removing sublc-list from index 0 in lc-list1, dummyHead.next = lc-list2
        ListNode dummyHead = new ListNode(-1, lc-list1);        

        //traverse to left sublc-list of lc-list1, which left.next is ListNode to be removed at index a.
        ListNode l = dummyHead;
        for(int i = 0; i < a; i++) {
            l = l.next;
        }

        //traverse to right sublc-list of lc-list1, which right is ListNode to be removed at index b.
        ListNode r = l;
        for(int i = 0; i < (b - a + 1); i++) {
            r = r.next;
        }

        //The last (not null) node in lc-list2
        ListNode lc-list2LastNode = lc-list2;
        while(lc-list2LastNode.next != null) {
            lc-list2LastNode = lc-list2LastNode.next;
        }

        l.next = lc-list2;
        lc-list2LastNode.next = r.next;

        return dummyHead.next;
    }
}