题目描述（困难难度）

和上一道可以说是一个问题，只不过这个是给一个已经合并好的列表，然后给一个新的节点依据规则加入到合并好的列表。

解法一

对应 56 题的解法一，没看的话，可以先过去看一下。这个问题其实就是我们解法中的一个子问题，所以直接加过来就行了。

时间复杂度：O（n）。

空间复杂度： O（n），里边的 in 变量用来存储囊括的节点时候耗费的。

我们其实可以利用迭代器，一边遍历，一边删除，这样就不需要 in 变量了。

空间复杂度： O（1）。

对应 56 题的解法二，考虑到它给定的合并的列表是有序的，和解法二是一个思想。只不过这里不能直接从末尾添加，而是根据新节点的 start 来找到它应该在的位置，然后再利用之前的想法就够了。

这里把 leetcode 里的两种写法，贴过来，大家可以参考一下。

。

第二种。和之前是一样的思想，只不过更加的简洁，可以参考一下。

时间复杂度：O（n）。

空间复杂度：O（n），存储最后的结果。

总的来说，这道题可以看做上道题的一些变形，本质上是一样的。由于用 for 循环不能一边遍历列表，一边删除某个元素，所以利用迭代器实现边遍历，边删除，自己也是第一次用。此外，解法一更加通用些，它不要求给定的列表有序。

添加好友一起进步~

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击这里查看详情