题解 | #牛群的新结构# 模拟

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param list1 ListNode类
     * @param list2 ListNode类
     * @param a int整型
     * @param b int整型
     * @return ListNode类
     */
    ListNode* mergeInBetween(ListNode* list1, ListNode* list2, int a, int b) {
        // 哑结点，方便删除头结点
        auto dummyNode = new ListNode(0);
        dummyNode->next = list1;
        // 要删除的 a 结点的前置结点
        ListNode* pre = dummyNode;
        // 要删除的 b 结点的后置结点
        auto nxt = new ListNode(0);
        // 找到 pre
        for (int i = 0; i < a; i++) {
            pre = pre->next;
        }
        // 找到 nxt
        for (int i = 0; i <= b; i++) {
            list1 = list1->next;
        }
        nxt = list1;
        // 拼接
        pre->next = list2;
        // 找到 list2 的最后一个结点
        while (list2->next) {
            list2 = list2->next;
        }
        // 拼接
        list2->next = nxt;
        return dummyNode->next;
    }
};

时间复杂度：O(n1+n2)，最坏情况下，需要遍历 list1 和 list2 的全部

空间复杂度：O(1)，仅需几个额外的结点