Merge In Between Linked Lists

Medium Linked List Miscellaneous Original on LeetCode

Reported atOracle

Merge In Between Linked Lists is a medium linked list problem solved with the miscellaneous pattern. The best approach, optimal (splice in place), runs in O(n + m) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (rebuild through an array) up.

Problem

You are given two singly linked lists, list1 and list2, and two indices a and b (0-based). Remove the nodes of list1 at positions a through b, inclusive, and put the whole of list2 in their place.

Return the head of the resulting list. Neither the first nor the last node of list1 is ever removed.

Examples

Example 1

Input
list1 = [4, 8, 15, 16, 23, 42], a = 2, b = 3, list2 = [7, 9]
Output
[4, 8, 7, 9, 23, 42]
Why
Nodes at indices 2 and 3 (values 15 and 16) are cut out and [7, 9] is spliced into the gap.

Example 2

Input
list1 = [1, 2, 3], a = 1, b = 1, list2 = [50, 60, 70]
Output
[1, 50, 60, 70, 3]
Why
Only the middle node is removed; all of list2 goes where it was.

Constraints

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

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (rebuild through an array)O(n + m)O(n + m)
Optimal (splice in place)O(n + m)O(1)

1Brute force (rebuild through an array)

TimeO(n + m)Each node of both lists is visited a constant number of times.
SpaceO(n + m)The value array and the brand-new list hold n + m entries.

Copy the values you want to keep into an array in the final order: list1 before index a, all of list2, then list1 after index b. Build a fresh linked list from that array.

  1. Walk list1 with an index; add values with index < a to the array.
  2. Add every value of list2.
  3. Walk list1 again; add values with index > b.
  4. Create new nodes from the array behind a dummy head and return dummy.next.
class Solution {
    public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
        List<Integer> vals = new ArrayList<>();
        int i = 0;
        for (ListNode p = list1; p != null; p = p.next, i++) {
            if (i < a) vals.add(p.val);
        }
        for (ListNode p = list2; p != null; p = p.next) vals.add(p.val);
        i = 0;
        for (ListNode p = list1; p != null; p = p.next, i++) {
            if (i > b) vals.add(p.val);
        }
        ListNode dummy = new ListNode(0), tail = dummy;
        for (int v : vals) {
            tail.next = new ListNode(v);
            tail = tail.next;
        }
        return dummy.next;
    }
}

2Optimal (splice in place)

TimeO(n + m)At most one walk through list1 (up to index b + 1) and one through list2.
SpaceO(1)Only three pointers; the existing nodes are relinked.

Find the node at index a - 1 (before) and the node at index b + 1 (after) in list1, and the last node of list2. Point before.next at list2's head and the tail's next at after. No new nodes are created.

  1. Walk a - 1 steps from list1 to get before.
  2. From before, walk b - a + 2 more steps to get after (the node at index b + 1).
  3. Walk list2 to its last node, tail2.
  4. Set before.next = list2 and tail2.next = after; return list1.
class Solution {
    public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
        ListNode before = list1;
        for (int i = 0; i < a - 1; i++) before = before.next;
        ListNode after = before;
        for (int i = 0; i < b - a + 2; i++) after = after.next;
        ListNode tail2 = list2;
        while (tail2.next != null) tail2 = tail2.next;
        before.next = list2;
        tail2.next = after;
        return list1;
    }
}

Edge cases to test

  • a == b: exactly one node is removed
  • a = 1 and b = length - 2: everything but the first and last node is replaced
  • list2 has a single node

Hints

Hint 1

You need two anchors in list1: the node just before index a and the node just after index b.

Hint 2

You also need the tail of list2, so the node after b can be hooked onto it.

Hint 3

Once you have the three nodes, the splice is two pointer assignments.

FAQ

What is the best time complexity for Merge In Between Linked Lists?

Optimal (splice in place) runs in O(n + m) time and O(1) extra space. At most one walk through list1 (up to index b + 1) and one through list2.

Which pattern does Merge In Between Linked Lists use?

It is a linked list problem that uses the miscellaneous pattern. Other problems with the same pattern: Delete Node in a Linked List, Copy List with Random Pointer, Intersection of Two Linked Lists.

Is there a brute force solution for Merge In Between Linked Lists?

Yes. Brute force (rebuild through an array) takes O(n + m) time and O(n + m) space. Copy the values you want to keep into an array in the final order: list1 before index a, all of list2, then list1 after index b.

Which edge cases should I test for Merge In Between Linked Lists?

a == b: exactly one node is removed; a = 1 and b = length - 2: everything but the first and last node is replaced; list2 has a single node.