1669. Merge In Between Linked Lists

1669. Merge In Between Linked Lists (Medium)

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

Remove list1's nodes from the ath node to the bth node, and put list2 in their place.

The blue edges and nodes in the following figure incidate the result:

Build the result list and return its head.

 

Example 1:

Input: list1 = [0,1,2,3,4,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
Output: [0,1,2,1000000,1000001,1000002,5]
Explanation: We remove the nodes 3 and 4 and put the entire list2 in their place. The blue edges and nodes in the above figure indicate the result.

Example 2:

Input: list1 = [0,1,2,3,4,5,6], a = 2, b = 5, list2 = [1000000,1000001,1000002,1000003,1000004]
Output: [0,1,1000000,1000001,1000002,1000003,1000004,6]
Explanation: The blue edges and nodes in the above figure indicate the result.

 

Constraints:

• 3 <= list1.length <= 104
• 1 <= a <= b < list1.length - 1
• 1 <= list2.length <= 104

Related Topics:
Linked List

Solution 1.

Find the following pointers:

• p where p->next points to ath node.
• q where p points to bth node.

Then we can stitch them together by assigning:

• B to p->next
• q->next to the next pointer of B's tail node.

// OJ: https://leetcode.com/problems/merge-in-between-linked-lists/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    ListNode* mergeInBetween(ListNode* A, int a, int b, ListNode* B) {
        ListNode *q = A, *p = NULL;
        for (int i = 0; i < b; ++i) {
            if (i == a - 1) p = q;
            q = q->next;
        }
        p->next = B;
        while (B->next) B = B->next;
        B->next = q->next;
        return A;
    }
};