力扣1669合並兩個鏈錶筆記

給你兩個鏈錶 list1 和 list2 ，它們包含的元素分別為 n 個和 m 個。

請你將 list1 中下標從 a 到 b 的全部節點都删除，並將list2 接在被删除節點的比特置。

下圖中藍色邊和節點展示了操作後的結果：

請你返回結果鏈錶的頭指針。

示例 1：

輸入：list1 = [0,1,2,3,4,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
輸出：[0,1,2,1000000,1000001,1000002,5]
解釋：我們删除 list1 中下標為 3 和 4 的兩個節點，並將 list2 接在該比特置。上圖中藍色的邊和節點為答案鏈錶。

示例 2：

輸入：list1 = [0,1,2,3,4,5,6], a = 2, b = 5, list2 = [1000000,1000001,1000002,1000003,1000004]
輸出：[0,1,1000000,1000001,1000002,1000003,1000004,6]
解釋：上圖中藍色的邊和節點為答案鏈錶。

來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/merge-in-between-linked-lists
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

 題意是要在一個鏈錶中删除一段並加入另一段

首先要知道删除的起始端和終點端

找到起始端和終點端後將起始端與另一段的起始端連接，再將終點端與另一段的終點端連接起來即可

class Solution {
    public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
        ListNode before = list1, after = list1;
        //before代錶前半段，after代錶後半段
        for (int i = 1; i < a; i++) {
            before = before.next;
        }
        //從1到a-1遍曆（一共a-1次）找到插入段的頭部
        for (int i = 0; i <= b; i++) {
            after = after.next;
        }
        //從0到b遍曆（一共b+1次）找到插入段的尾部
        ListNode begin = list2, end = list2;
        //begin代錶list2的開始，end代錶list2的結束
        while (end.next != null) {
            end = end.next;
        }
        //找到插入段的尾部，即第一個鏈錶後半段的頭部
        before.next = begin;
        end.next = after;
        //收尾依次相連
        return list1;
    }
}

在題解中找到了更優的方法，比較發現，這種方法好在第二次找b節點後面的節點時直接以第一次找的a-1節點開始，省去了重複的步驟，時間短，占用內存少

class Solution {
    public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
        ListNode cur = list1;
        int count = b - a + 2;
        // 找到list1中第a個節點的前一個節點
        while ((a - 1) > 0) {
            a--;
            cur = cur.next;
        }
        ListNode left = cur;
        // 找到list1中第b個節點的後一個節點
        while (count > 0) {
            cur = cur.next;
            count--;
        }
        ListNode right = cur; 
        // 將list1中第a個節點的前一個節點指向list2的頭節點
        left.next = list2;
        // 找到list2的尾節點
        while(list2.next != null) {
            list2 = list2.next;
        }
        // 將list2的尾節點指向list1中第b個節點的後一個節點
        list2.next = right;
        return list1;
    }
}