# 移除元素

给你一个数组 $nums$ 和一个值 $val$，你需要 原地 移除所有数值等于 $val$ 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 $O(1)$ 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

 

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。



你可以想象内部操作如下:

```
// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}
``` 

示例 1：

输入：`nums = [3,2,2,3], val = 3`

输出：2, `nums = [2,2]`

解释：函数应该返回新的长度 `2`, 并且 `nums` 中的前两个元素均为 `2`。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 `2` ，而 `nums = [2,2,3,3]` 或 `nums = [2,2,0,0]`，也会被视作正确答案。

示例 2：

输入：`nums = [0,1,2,2,3,0,4,2], val = 2`

输出：5, `nums = [0,1,3,0,4]`

解释：函数应该返回新的长度 `5`, 并且 `nums` 中的前五个元素为 `0, 1, 3, 0, 4`。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
 

提示：

`0 <= nums.length <= 100`

`0 <= nums[i] <= 50`

`0 <= val <= 100`

![移除元素](https://qncdn.oleehu.xyz/blog/LeetCode/%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0.png)


```c++
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        vector<int>::iterator it;
        for (it = nums.begin(); it != nums.end(); ) {
            if (*it == val) {

                it = nums.erase(it);
            }
            else{
                it++;
            }
        }
        return nums.size();
    }
};
```

时间复杂度为 `O(n)`，其中 `n` 是输入数组 `nums` 的长度。这是因为代码中的主要循环遍历整个数组，并在必要时执行删除操作，但删除操作的时间复杂度为 `O(1)`。所以总体时间复杂度是 `O(n)`。

空间复杂度为 `O(1)`，因为除了输入数组之外，算法没有使用任何额外的空间。

# 题解一：双指针

作者：力扣官方题解

链接：https://leetcode.cn/problems/remove-element/solutions/730203/yi-chu-yuan-su-by-leetcode-solution-svxi/

来源：力扣（LeetCode）

思路及算法

由于题目要求删除数组中等于 $val$ 的元素，因此输出数组的长度一定小于等于输入数组的长度，我们可以把输出的数组直接写在输入数组上。可以使用双指针：右指针 $right$ 指向当前将要处理的元素，左指针 $left$指向下一个将要赋值的位置。

如果右指针指向的元素不等于 $val$，它一定是输出数组的一个元素，我们就将右指针指向的元素复制到左指针位置，然后将左右指针同时右移；

如果右指针指向的元素等于 $val$，它不能在输出数组里，此时左指针不动，右指针右移一位。

整个过程保持不变的性质是：区间 $[0,left)$ 中的元素都不等于 $val$。当左右指针遍历完输入数组以后，$left$ 的值就是输出数组的长度。

这样的算法在最坏情况下（输入数组中没有元素等于 $val$，左右指针各遍历了数组一次。

![移除元素(题解一)](https://qncdn.oleehu.xyz/blog/LeetCode/%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0%EF%BC%88%E9%A2%98%E8%A7%A3%E4%B8%80%EF%BC%89.png)


```c++
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int n = nums.size();
        int left = 0;
        for (int right = 0; right < n; right++) {
            if (nums[right] != val) {
                nums[left] = nums[right];
                left++;
            }
        }
        return left;
    }
};

```
复杂度分析

时间复杂度：$O(n)$，其中 $n$ 为序列的长度。我们只需要遍历该序列至多两次。

空间复杂度：$O(1)$。我们只需要常数的空间保存若干变量。

# 题解二：双指针优化

作者：力扣官方题解

链接：https://leetcode.cn/problems/remove-element/solutions/730203/yi-chu-yuan-su-by-leetcode-solution-svxi/

来源：力扣（LeetCode）


思路

如果要移除的元素恰好在数组的开头，例如序列 $[1,2,3,4,5]$，当 $val$ 为 $1$ 时，我们需要把每一个元素都左移一位。注意到题目中说：「元素的顺序可以改变」。实际上我们可以直接将最后一个元素 $5$ 移动到序列开头，取代元素 $1$，得到序列 $[5,2,3,4]$，同样满足题目要求。这个优化在序列中 $val$ 元素的数量较少时非常有效。

实现方面，我们依然使用双指针，两个指针初始时分别位于数组的首尾，向中间移动遍历该序列。

算法

如果左指针 $left$ 指向的元素等于 $val$，此时将右指针 $right$ 指向的元素复制到左指针 $left$ 的位置，然后右指针 $right$ 左移一位。如果赋值过来的元素恰好也等于 $val$，可以继续把右指针 $right$ 指向的元素的值赋值过来（左指针 $left$ 指向的等于 $val$ 的元素的位置继续被覆盖），直到左指针指向的元素的值不等于 $val$ 为止。

当左指针 $left$ 和右指针 $right$ 重合的时候，左右指针遍历完数组中所有的元素。

这样的方法两个指针在最坏的情况下合起来只遍历了数组一次。与方法一不同的是，方法二避免了需要保留的元素的重复赋值操作。


![移除元素(题解二)](https://qncdn.oleehu.xyz/blog/LeetCode/%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0%EF%BC%88%E9%A2%98%E8%A7%A3%E4%BA%8C%EF%BC%89.png)

```c++
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int left = 0, right = nums.size();
        while (left < right) {
            if (nums[left] == val) {
                nums[left] = nums[right - 1];
                right--;
            } else {
                left++;
            }
        }
        return left;
    }
};

```

复杂度分析

时间复杂度：$O(n)$，其中$n$ 为序列的长度。我们只需要遍历该序列至多一次。

空间复杂度：$O(1)$。我们只需要常数的空间保存若干变量。

LeetCode（移除元素）

# 仿真阶段

systemC应用程序有三个运行阶段:
1. 精化:执行sc_start()之前的语句。

其主要目的是创建内部数据结构来支持模拟的语义。

在精化过程中，将创建模块层次结构的各个部分(模块、端口、原始通道和流程)，并且将端口和导出绑定到通道。

2. 执行:进一步分为两个阶段:

1)初始化

仿真内核识别所有仿真进程，并将它们置于可运行或等待进程集中。

除了那些请求“不初始化”的进程外，所有模拟进程都处于可运行集。

b)仿真

通常被描述为调度进程运行的状态机，并提前模拟时间。它有两个内部阶段:



1)评估:一次运行所有可运行进程。每个进程运行直到达到wait()或return。如果没有可运行进程，则停止。

2) advance-time:一旦可运行进程集被清空，模拟进入advance-time阶段，它做:

A)将模拟时间移动到与计划事件最接近的时间

B)将等待特定时间的进程移动到可运行集中

C)回到评价阶段

从evaluate到advance-time的过程一直持续到三种情况中的一种发生。然后进入清理阶段。

A，所有的过程都产生了

B)进程执行了sc_stop()

C)达到最大时间

3. 清理或后处理:销毁对象，释放内存，关闭打开的文件等。

内核在精化和仿真的不同阶段调用四个回调函数。他们有下列声明:

1. 虚void before_end_of_elaboration():在模块层次结构构造之后调用

2. 虚拟void end_of_elaboration():在细化的最后，在所有回调before_end_of_elaboration完成之后，在这些回调执行的任何实例化或端口绑定完成之后，在开始模拟之前调用。

3. 虚拟无效start_of_simulation():

A)当应用程序第一次调用sc_start或在模拟开始时立即调用，如果模拟是在内核的直接控制下启动的。

B)如果应用程序多次调用sc_start，则在第一次调用sc_start时调用start_of_simulation。

C)在回调end_of_elaboration之后，在调用调度器的初始化阶段之前调用。

4. 虚拟void end_of_simulation():

A)在调度程序因为sc_stop而停止时调用，或者在模拟即将结束时调用，如果模拟是在内核的直接控制下启动的。

B)即使sc_stop被多次调用，也只调用一次。

# Simulation_Stages.cpp


```c++
#include <systemc>
using namespace sc_core;

SC_MODULE(STAGE) {
  SC_CTOR(STAGE) { // 阐述
    std::cout << sc_time_stamp() << ": Elaboration: constructor" << std::endl;
    SC_THREAD(thread); // 初始化 + 模拟
  }
  ~STAGE() { // 清理
    std::cout << sc_time_stamp() << ": Cleanup: desctructor" << std::endl;
  }
  void thread() {
    std::cout << sc_time_stamp() << ": Execution.initialization" << std::endl;
    int i = 0;
    while(true) {
      wait(1, SC_SEC); // 提前时间
      std::cout << sc_time_stamp() << ": Execution.simulation" << std::endl; // evaluation
      if (++i >= 2) {
        sc_stop(); // 2 次迭代后停止模拟
      }
    }
  }
  void before_end_of_elaboration() {
    std::cout << "before end of elaboration" << std::endl;
  }
  void end_of_elaboration() {
    std::cout << "end of elaboration" << std::endl;
  }
  void start_of_simulation() {
    std::cout << "start of simulation" << std::endl;
  }
  void end_of_simulation() {
    std::cout << "end of simulation" << std::endl;
  }
};

int sc_main(int, char*[]) {
  STAGE stage("stage"); // 阐述
  sc_start(); // 执行到sc_stop
  return 0; // 清理
}
```

# 结果


```shell

        SystemC 2.3.3-Accellera --- Oct  4 2020 22:59:38
        Copyright (c) 1996-2018 by all Contributors,
        ALL RIGHTS RESERVED
0 s: Elaboration: constructor
before end of elaboration
end of elaboration
start of simulation
0 s: Execution.initialization
1 s: Execution.simulation
2 s: Execution.simulation

Info: /OSCI/SystemC: Simulation stopped by user.
end of simulation
2 s: Cleanup: desctructor
```

SystemC入门（七）——仿真阶段

# 删除排序数组中的重复项

给你一个 非严格递增排列 的数组 $nums$ ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 $nums$ 中唯一元素的个数。

考虑 $nums$ 的唯一元素的数量为 $k$ ，你需要做以下事情确保你的题解可以被通过：

更改数组 $nums$ ，使 $nums$ 的前 $k$ 个元素包含唯一元素，并按照它们最初在 $nums$ 中出现的顺序排列。$nums$ 的其余元素与 $nums$ 的大小不重要。
返回 $k$ 。
判题标准:



系统会用下面的代码来测试你的题解:

`int[] nums = [...]`; // 输入数组

`int[] expectedNums = [...]`; // 长度正确的期望答案

`int k = removeDuplicates(nums)`; // 调用

`assert k == expectedNums.length`;

```
for(int i = 0; i < k; i++){$
  assert nums[i] == expectedNums[i];   
}
```
如果所有断言都通过，那么您的题解将被 通过。

 

示例 1：

输入：`nums = [1,1,2]`

输出：2, `nums = [1,2,_]`

解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2：

输入：`nums = [0,0,1,1,1,2,2,3,3,4]`

输出：5, `nums = [0,1,2,3,4]`

解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
 

提示：

`1 <= nums.length <= 3 * 104`

`-104 <= nums[i] <= 104`

$nums$ 已按 非严格递增 排列

![删除排序数组中的重复项](https://qncdn.oleehu.xyz/blog/LeetCode/%E5%88%A0%E9%99%A4%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E4%B8%AD%E7%9A%84%E9%87%8D%E5%A4%8D%E9%A1%B9.png)


```c++
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.empty()){return 0;}
       for (vector<int>::iterator it = nums.begin()+1; it != nums.end();){
           if(*it==*(it-1)){
               it = nums.erase(it);
           }
           else{it++;}
       }
        int k=nums.size();
        return k;
    }
};
```

# 题解：双指针

作者：力扣官方题解

链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-array/solutions/728105/shan-chu-pai-xu-shu-zu-zhong-de-zhong-fu-tudo/

来源：力扣（LeetCode）


这道题目的要求是：对给定的有序数组 $nums$ 删除重复元素，在删除重复元素之后，每个元素只出现一次，并返回新的长度，上述操作必须通过原地修改数组的方法，使用 $O(1)$ 的空间复杂度完成。

由于给定的数组 $nums$ 是有序的，因此对于任意 $i<j$，如果 $nums[i]=nums[j]$，则对任意 $i≤k≤j$，必有 $nums[i]=nums[k]=nums[j]$，即相等的元素在数组中的下标一定是连续的。利用数组有序的特点，可以通过双指针的方法删除重复元素。

如果数组 $nums$ 的长度为 $0$，则数组不包含任何元素，因此返回 $0$。

当数组 $nums$ 的长度大于 $0$ 时，数组中至少包含一个元素，在删除重复元素之后也至少剩下一个元素，因此 $nums[0]$ 保持原状即可，从下标 $1$ 开始删除重复元素。

定义两个指针 $fast$ 和 $slow$ 分别为快指针和慢指针，快指针表示遍历数组到达的下标位置，慢指针表示下一个不同元素要填入的下标位置，初始时两个指针都指向下标 $1$。

假设数组 $nums$ 的长度为 nnn。将快指针 $fast$ 依次遍历从 $1$ 到 $n−1$ 的每个位置，对于每个位置，如果 $nums[fast]≠nums[fast−1]$，说明 $nums[fast]$ 和之前的元素都不同，因此将 $nums[fast]$ 的值复制到 $nums[slow]$，然后将 $slow$ 的值加 111，即指向下一个位置。

遍历结束之后，从 $nums[0]$ 到 $nums[slow−1]$ 的每个元素都不相同且包含原数组中的每个不同的元素，因此新的长度即为 $slow$，返回 $slow$ 即可。

![删除排序数组中的重复项(题解)](https://qncdn.oleehu.xyz/blog/LeetCode/%E5%88%A0%E9%99%A4%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E4%B8%AD%E7%9A%84%E9%87%8D%E5%A4%8D%E9%A1%B9%EF%BC%88%E9%A2%98%E8%A7%A3%EF%BC%89.png)


```c++
class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int fast = 1, slow = 1;
        while (fast < n) {
            if (nums[fast] != nums[fast - 1]) {
                nums[slow] = nums[fast];
                ++slow;
            }
            ++fast;
        }
        return slow;
    }
}
```

复杂度分析

时间复杂度：$O(n)$，其中 $n$ 是数组的长度。快指针和慢指针最多各移动 $n$ 次。

空间复杂度：$O(1)$。只需要使用常数的额外空间。

LeetCode（删除排序数组中的重复项）

# Simulation Process
Simulation Process:
1. 是sc_module类的成员函数，并且
3. 没有输入参数，也没有返回值，那么
2. 是否注册到模拟内核

如何注册一个Simulation Process:
1. SC_METHOD(func):没有自己的执行线程，不消耗模拟时间，不能挂起，不能调用调用wait()的代码。
2. SC_THREAD(func):有自己的执行线程，可能消耗模拟时间，可以挂起，并可以调用调用wait()的代码。
3. SC_CTHREAD(func, event): SC_THREAD的一种特殊形式，只能对时钟边缘事件具有静态敏感性



什么时候可以注册:
1. 在构造函数的主体中，
2. 在模块的before_end_of_elaboration或end_of_elaboration回调函数中，
3. 或在从构造函数或回调函数调用的成员函数中

限制:
1. 只能在同一个模块的成员函数上进行注册。
2. SC_CTHREAD不能从end_of_elaboration回调函数中调用。

注意:
1. SC_THREAD可以完成SC_METHOD或SC_CHTEAD所做的一切。我将在示例中主要使用这个过程。
2. 为了SC_THREAD或SC_CTHREAD进程被再次调用，应该有一个while循环确保它永远不会退出。
3. SC_THREAD进程不需要while循环。next_trigger()会再次调用它。
4. systemC中的模拟时间不是程序运行的实际时间。它是一个由模拟内核管理的计数器。稍后再解释。

# Simulation_Process.cpp


```c++
#include <systemc>
using namespace sc_core;

SC_MODULE(PROCESS) {
  sc_clock clk; // 声明时钟
  SC_CTOR(PROCESS) : clk("clk", 1, SC_SEC) { // 实例化具有 1 秒周期性的时钟
    SC_METHOD(method); // 注册方法
    SC_THREAD(thread); // 注册线程
    SC_CTHREAD(cthread, clk); // 注册时钟线程
  }
  void method(void) { // 定义方法成员函数
    // 这里没有 while 循环
    std::cout << "method triggered @ " << sc_time_stamp() << std::endl;
    next_trigger(sc_time(1, SC_SEC)); // 1 秒后触发
  }
  void thread() { // 定义线程成员函数
    while (true) { // 无限循环确保它永远不会退出
      std::cout << "thread triggered @ " << sc_time_stamp() << std::endl;
      wait(1, SC_SEC); // 等待 1 秒钟，然后再次执行
    }
  }
  void cthread() { // 定义 CTHREAD 成员函数
    while (true) { // 无限循环
      std::cout << "cthread triggered @ " << sc_time_stamp() << std::endl;
      wait(); // 等待下一个 CLK 事件，该事件在 1 秒后出现
    }
  }
};

int sc_main(int, char*[]) {
  PROCESS process("process"); // 初始化模块
  std::cout << "execution phase begins @ " << sc_time_stamp() << std::endl;
  sc_start(2, SC_SEC); // 运行模拟 2 秒
  std::cout << "execution phase ends @ " << sc_time_stamp() << std::endl;
  return 0;
}

```
# 结果


```shell
        SystemC 2.3.3-Accellera --- Oct  4 2020 22:59:38
        Copyright (c) 1996-2018 by all Contributors,
        ALL RIGHTS RESERVED
execution phase begins @ 0 s
method triggered @ 0 s
thread triggered @ 0 s
cthread triggered @ 0 s
method triggered @ 1 s
thread triggered @ 1 s
cthread triggered @ 1 s
execution phase ends @ 2 s
```

SystemC入门（六）——Simulation Process

# 合并两个有序列表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例 1：


输入：`l1 = [1,2,4], l2 = [1,3,4]`

输出：`[1,1,2,3,4,4]`

示例 2：

输入：`l1 = [], l2 = []`

输出：`[]`

示例 3：

输入：`l1 = [], l2 = [0]`

输出：`[0]`
 



提示：

两个链表的节点数目范围是 `[0, 50]`

`-100 <= Node.val <= 100`

`l1` 和 `l2` 均按 非递减顺序 排列

![合并两个有序列表](https://qncdn.oleehu.xyz/blog/LeetCode/%E5%90%88%E5%B9%B6%E4%B8%A4%E4%B8%AA%E6%9C%89%E5%BA%8F%E5%88%97%E8%A1%A8.png)


```c++
/**
 * 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* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (list1 == nullptr) return list2;
        if (list2 == nullptr) return list1;

        ListNode* list;
        ListNode* tlist;

        if (list1->val <= list2->val) {
            list = list1;
            tlist = list1;
            list1 = list1->next;
        } else {
            list = list2;
            tlist = list2;
            list2 = list2->next;
        }
        
        while (list1 != nullptr && list2 != nullptr) {
            if (list1->val <= list2->val) {
                tlist->next = list1;
                list1 = list1->next;
            } else {
                tlist->next = list2;
                list2 = list2->next;
            }
            tlist = tlist->next;
        }
        
        if (list1 == nullptr)
            tlist->next = list2;
        else
            tlist->next = list1;

        return list;
    }
};

```


:::tip{title="提示"}
在 `C++` 中，不能像在数组上那样简单地对指针执行增量操作（例如 `list1++` 或 `list2++`）。这些操作适用于指向数组元素的指针，而不是链表节点。对于链表，应该使用 `->next` 来访问下一个节点。

变量定义在在 `if` 和 `else`以及`while`等 语句块内部。这意味着在其它地方无法访问它们。

小心指针变为空指针导致了空指针访问异常。
:::

# 题解一：递归

作者：力扣官方题解

链接：https://leetcode.cn/problems/merge-two-sorted-lists/solutions/226408/he-bing-liang-ge-you-xu-lian-biao-by-leetcode-solu/

来源：力扣（LeetCode）

思路

我们可以如下递归地定义两个链表里的 merge 操作（忽略边界情况，比如空链表等）：

$$
\begin{cases}\text { list } 1[0]+\text { merge }(\text { list } 1[1:], \text { list } 2) & \text { list } 1[0]<\text { list } 2[0] \\ \text { list } 2[0]+\text { merge }(\text { list } 1, \text { list } 2[1:]) & \text { otherwise }\end{cases}
$$

也就是说，两个链表头部值较小的一个节点与剩下元素的 $merge$ 操作结果合并。

算法

我们直接将以上递归过程建模，同时需要考虑边界情况。

如果 $l1$ 或者 $l2$ 一开始就是空链表 ，那么没有任何操作需要合并，所以我们只需要返回非空链表。否则，我们要判断 $l1$ 和 $l2$ 哪一个链表的头节点的值更小，然后递归地决定下一个添加到结果里的节点。如果两个链表有一个为空，递归结束。

![合并两个有序列表(题解一)](https://qncdn.oleehu.xyz/blog/LeetCode/%E5%90%88%E5%B9%B6%E4%B8%A4%E4%B8%AA%E6%9C%89%E5%BA%8F%E5%88%97%E8%A1%A8%EF%BC%88%E9%A2%98%E8%A7%A3%E4%B8%80%29.png)
```c++
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == nullptr) {
            return l2;
        } else if (l2 == nullptr) {
            return l1;
        } else if (l1->val < l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

```

复杂度分析

时间复杂度：$O(n+m)$，其中 $n$ 和 $m$ 分别为两个链表的长度。因为每次调用递归都会去掉 $l1$ 或者 $l2$ 的头节点（直到至少有一个链表为空），函数 $mergeTwoList$ 至多只会递归调用每个节点一次。因此，时间复杂度取决于合并后的链表长度，即 $O(n+m)$。

空间复杂度：$O(n+m)$，其中 $n$ 和 $m$ 分别为两个链表的长度。递归调用 $mergeTwoLists$ 函数时需要消耗栈空间，栈空间的大小取决于递归调用的深度。结束递归调用时 $mergeTwoLists$ 函数最多调用 $n+m$ 次，因此空间复杂度为 $O(n+m)$。

# 题解二：迭代

作者：力扣官方题解

链接：https://leetcode.cn/problems/merge-two-sorted-lists/solutions/226408/he-bing-liang-ge-you-xu-lian-biao-by-leetcode-solu/

来源：力扣（LeetCode）

思路

我们可以用迭代的方法来实现上述算法。当 $l1$ 和 $l2$ 都不是空链表时，判断 $l1$ 和 $l2$ 哪一个链表的头节点的值更小，将较小值的节点添加到结果里，当一个节点被添加到结果里之后，将对应链表中的节点向后移一位。

算法

首先，我们设定一个哨兵节点 $prehead$ ，这可以在最后让我们比较容易地返回合并后的链表。我们维护一个 $prev$ 指针，我们需要做的是调整它的 $next$ 指针。然后，我们重复以下过程，直到 $l1$ 或者 $l2$ 指向了 $null$ ：如果 $l1$ 当前节点的值小于等于 $l2$ ，我们就把 $l1$ 当前的节点接在 prev 节点的后面同时将 $l1$ 指针往后移一位。否则，我们对 $l2$ 做同样的操作。不管我们将哪一个元素接在了后面，我们都需要把 $prev$ 向后移一位。

在循环终止的时候， $l1$ 和 $l2$ 至多有一个是非空的。由于输入的两个链表都是有序的，所以不管哪个链表是非空的，它包含的所有元素都比前面已经合并链表中的所有元素都要大。这意味着我们只需要简单地将非空链表接在合并链表的后面，并返回合并链表即可。

![合并两个有序列表(题解一)](https://qncdn.oleehu.xyz/blog/LeetCode/%E5%90%88%E5%B9%B6%E4%B8%A4%E4%B8%AA%E6%9C%89%E5%BA%8F%E5%88%97%E8%A1%A8%EF%BC%88%E9%A2%98%E8%A7%A3%E4%BA%8C%EF%BC%89.png)


```c++
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* preHead = new ListNode(-1);

        ListNode* prev = preHead;
        while (l1 != nullptr && l2 != nullptr) {
            if (l1->val < l2->val) {
                prev->next = l1;
                l1 = l1->next;
            } else {
                prev->next = l2;
                l2 = l2->next;
            }
            prev = prev->next;
        }

        // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev->next = l1 == nullptr ? l2 : l1;

        return preHead->next;
    }
};

```

复杂度分析

时间复杂度：$O(n+m)$，其中 $n$ 和 $m$ 分别为两个链表的长度。因为每次循环迭代中，$l1$ 和 $l2$ 只有一个元素会被放进合并链表中， 因此 $while$ 循环的次数不会超过两个链表的长度之和。所有其他操作的时间复杂度都是常数级别的，因此总的时间复杂度为 $O(n+m)$。

空间复杂度：$O(1)$。我们只需要常数的空间存放若干变量。