# 【LeetCode】 1669. Merge In Between Linked Lists

## Description
> 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 indicate the result:
> Build the result list and return its head.

> Constraints:
> * `3 <= list1.length <= 10^4`
> * `1 <= a <= b < list1.length - 1`
> * `1 <= list2.length <= 10^4`

> 給你兩個 linked lists：`list1` 和 `list2`，大小分別為 `n` 和 `m`。
> 移除 `list1` 從第 `ath` 到第 `bth` 的節點，並將 `list2` 取代它們的位置。
> 圖中藍色的邊和節點就是結果。
> 建構出答案的 list 並回傳它的開頭。

> 限制：
> * `3 <= list1.length <= 10^4`
> * `1 <= a <= b < list1.length - 1`
> * `1 <= list2.length <= 10^4`

## Example:


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.

## Solution

* 不需要把多餘的節點移除做記憶體管理，因此只要想辦法建構出答案的 linked list 即可。
* linked list 的更改與陣列不同，不需要每個節點都做修正，只需要針對斷點前後的 node 去修正 `next` 即可。
* 參考題目第一張圖，我們只需要將 `list1` 的 `a - 1` 節點的 `next` 指向 `list2` 的開頭，並將 `list2` 結尾節點的 `next` 指向 `list1` 的 `b + 1` 節點就完成了。
* 因為限制的關係，不需要特別考慮邊緣測資。

### Code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeInBetween(ListNode* list1, int a, int b, ListNode* list2) {
        ListNode* pre_a = list1;
        ListNode* next_b = list1;
        for(int i = 0; i < b + 1; i++)
        {
            if(i < a - 1)
                pre_a = pre_a->next;
            next_b = next_b->next;
        }
        pre_a->next = list2;
        while(list2->next)
            list2 = list2->next;
        list2->next = next_b;
        return list1;
    }
};

###### tags: `LeetCode` `C++`