题目描述（中等难度）

给定一个列表，将有重叠部分的合并。例如[ [ 1 3 ] [ 2 6 ] ] 合并成 [ 1 6 ] 。

解法一

常规的思想，将大问题化解成小问题去解决。

假设给了一个大小为 n 的列表，然后我们假设 n - 1 个元素的列表已经完成了全部合并，我们现在要解决的就是剩下的 1 个，怎么加到已经合并完的 n -1 个元素中。

这样的话分下边几种情况， 我们把每个范围叫做一个节点，节点包括左端点和右端点。

1. 如下图，新加入的节点左端点和右端点，分别在两个节点之间。这样，我们只要删除这两个节点，并且使用左边节点的左端点，右边的节点的右端点作为一个新节点插入即可。也就是删除 [ 1 6 ] 和 [ 8 12 ] ，加入 [ 1 12 ] 到合并好的列表中。

2. 如下图，新加入的节点只有右端点在之前的一个节点之内，这样的话将这个节点删除，使用删除的节点的右端点，新加入的节点的左端点，作为新的节点插入即可。也就是删除 [ 8 12 ]，加入 [ 7 12 ] 到合并好的列表中。

   

3. 如下图，新加入的节点的左端点和右端点在之前的一个节点之内，这样的话新加入的节点舍弃就可以了。

4. 

以上就是所有的情况了，可以开始写代码了。

时间复杂度：O（n²）。

空间复杂度：O （n），用来存储结果。

解法二

参考这里的解法二。

在解法一中，我们每次对于新加入的节点，都用一个 for 循环去遍历已经合并好的列表。如果我们把之前的列表，按照左端点进行从小到大排序了。这样的话，每次添加新节点的话，我们只需要和合并好的列表最后一个节点对比就可以了。

排好序后我们只需要把新加入的节点和最后一个节点比较就够了。

情况 1，如果新加入的节点的左端点大于合并好的节点列表的最后一个节点的右端点，那么我们只需要把新节点直接加入就可以了。

情况 2 ，如果新加入的节点的左端点不大于合并好的节点列表的最后一个节点的右端点，那么只需要判断新加入的节点的右端点和最后一个节点的右端点哪个大，然后更新最后一个节点的右端点就可以了。

时间复杂度：O（n log（n）），排序算法。

空间复杂度：O（n），存储结果。另外排序算法也可能需要。

解法三

刷这么多题，第一次利用图去解决问题，这里分享下作者的思路。

如果每个节点如果有重叠部分，就用一条边相连。

我们用一个 HashMap，用邻接表的结构来实现图，类似于下边的样子。

图存起来以后，可以发现，最后有几个连通图，最后合并后的列表就有几个。我们需要把每个连通图保存起来，然后在每个连通图中找最小和最大的端点作为一个节点加入到合并后的列表中就可以了。最后，我们把每个连通图就转换成下边的图了。

时间复杂度：

空间复杂度：O（n²），最坏的情况，每个节点都互相重合，这样每个都与其他节点相连，就会是 n² 的空间存储图。

可惜的是，这种解法在 leetcode 会遇到超时错误。

总

开始的时候，使用最常用的思路，将大问题化解为小问题，然后用递归或者直接用迭代实现。解法二中，先对列表进行排序，从而优化了时间复杂度，也不是第一次看到了。解法三中，利用图解决问题很新颖，是我刷题第一次遇到的，又多了一种解题思路。

添加好友一起进步~

如果觉得有帮助的话，可以点击 给一个 star 哦 ^^