160. 56. 57. | 区间合并类型 LeetCode

 分析：

• 暴力解法，分别遍历两个链表，判断a链表是否有结点存在于b链表中。

• 哈希表解法，遍历a链表，将a链表的结点用哈希表存储，再遍历b链表，判断b链表中是否有结点存在于哈希表中。

• 双指针法：

• 该方法核心思路在于消除两个链表的长度差异，由题目可得知，链表的相交部分是相同的，存在差异的只有前面不重叠的那部分，而两个链表的长度是可能不同的。如果我们能够把长链表多出来的那部分差异给消除，就能够通过遍历来得到相交的部分。

• 设置两个指针，分别指向a，b两个链表；a，b两个指针同时遍历链表；当其中某个指针遍历到结尾的时候，将其指向另一个链表的起始位置；新的a，b指针继续遍历链表，直到另一个指针也遍历到结尾并指向另一个链表的起始位置；此时，a，b指针同时开始重新遍历链表，当a，b指针相同的时候，得到相交的结点。

  理解了双指针方法的核心思路后，我们可以对代码进行优化，只需要在一次遍历中，同时判断双指针是否到达了结尾，或者是相同。

分析：

  具体分析看官方已经讲解的十分详细，简单来讲就是连续区间在排序后一定互相临近，因此对可合并的连续区间，只需要求出其上界和下届即可。

https://leetcode-cn.com/problems/merge-intervals/solution/he-bing-qu-jian-by-leetcode-solution/

分析：

  题目提供的是已经排好序的区间列表，因此我们只需要将新的区间和列表中的区间进行比较，然后合并插入即可。

  我们只需要考虑三种情况：

1. 新区间不与当前区间重叠，则将当前区间添加到输出列表中；若新区间还未添加到输出列表中，则将新区间添加到输出列表中。

1. 新区间左边界大于当前区间的右边界

2. 新区间的右边界小于当前区间的左边界

2. 新区间与当前区间重叠，则合并两个区间，并将合并后的区间当做新区间，进行下一步判断。

3. 若新区间不与当前区间重叠，且循环已经结束，则将新区间添加到输出列表的最后面。

图解：

代码：