【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++