35-合并两个链表

​ a <= b

自己的做法

算法思想

找到list1 第a个节点的前一个节点，和第b个节点。注意节点是从0开始计数的，但是给定的a和b也是从0开始的。

添加一个哑节点dummy，因为头节点有可能被删除。

然后找到list2的尾节点，连接起来即可。

算法实现

class Solution {
public:
    ListNode* mergeInBetween(ListNode* list1, int a, int b, ListNode* list2) {
        ListNode * dummy = new ListNode();
        dummy->next = list1;
        ListNode * a_pre = dummy;
        for(int i = 0; i < a; i++) {
            a_pre = a_pre->next;
        }
        ListNode * b_node = a_pre;
        for(int i = 0; i < b - a + 1; i++) {
            b_node = b_node->next;
        }
        ListNode * end = list2;
        while (end->next) {
            end = end->next;
        }
        a_pre->next = list2;
        end->next = b_node->next;
        return dummy->next;
    }
};

算法性能

时间复杂度：$O(b + m)$。

空间复杂度：$O(1)$。

无参考做法。