和上一道可以说是一个问题，只不过这个是给一个已经合并好的列表，然后给一个新的节点依据规则加入到合并好的列表。
解法一
对应 56 题的解法一，没看的话，可以先过去看一下。这个问题其实就是我们解法中的一个子问题没看的话，可以先过去看一下。这个问题其实就是我们解法中的一个子问题，
所以直接加过来就行了
publicList<Interval>insert(List<Interval>intervals, IntervalnewInterval) { Intervalstart=null; Intervalend=null; inti_start=newInterval.start; inti_end=newInterval.end; intsize=intervals.size(); List<Interval>in=newArrayList<>(); //遍历合并好的列表for (intj=0; j<size; j++) { if (i_start>=intervals.get(j).start&&i_start<=intervals.get(j).end) { start=intervals.get(j); } if (i_end>=intervals.get(j).start&&i_end<=intervals.get(j).end) { end=intervals.get(j); } if (i_start<intervals.get(j).start&&i_end>intervals.get(j).end) { in.add(intervals.get(j)); } } if (in.size() !=0) { for (intindex=0; index<in.size(); index++) { intervals.remove(in.get(index)); } } Intervalinterval=null; //根据不同的情况，生成新的节点if (equals(start, end)) { ints=start==null?i_start : start.start; inte=end==null?i_end : end.end; interval=newInterval(s, e); } elseif (start!=null&&end!=null) { interval=newInterval(start.start, end.end); }elseif (start==null) { interval=newInterval(i_start, i_end); } if (start!=null) { intervals.remove(start); } if (end!=null) { intervals.remove(end); } //不同之处是生成的节点，要遍历原节点，根据 start 插入到对应的位置，虽然题目没说，但这里如果不按顺序插入的话，leetcode 过不了。for(inti=0;i<intervals.size();i++){ if(intervals.get(i).start>interval.start){ intervals.add(i,interval); returnintervals; } } intervals.add(interval); returnintervals; } privatebooleanequals(Intervalstart, Intervalend) { if (start==null&&end==null) { returnfalse; } if (start==null||end==null) { returntrue; } if (start.start==end.start&&start.end==end.end) { returntrue; } returnfalse; }
时间复杂度：O（n）。
空间复杂度： O（n）， 里边的 in 变量用来存储囊括的节点时候耗费的。
我们其实可以利用迭代器，一边遍历，一边删除，这样就不需要 in 变量了。
publicList<Interval>insert(List<Interval>intervals, IntervalnewInterval) { Intervalstart=null; Intervalend=null; inti_start=newInterval.start; inti_end=newInterval.end; //利用迭代器遍历for (Iterator<Interval>it=intervals.iterator(); it.hasNext();) { Intervalinter=it.next(); if (i_start>=inter.start&&i_start<=inter.end) { start=inter; } if (i_end>=inter.start&&i_end<=inter.end) { end=inter; } if (i_start<inter.start&&i_end>inter.end) { it.remove(); } } Intervalinterval=null; if (equals(start, end)) { ints=start==null?i_start : start.start; inte=end==null?i_end : end.end; interval=newInterval(s, e); } elseif (start!=null&&end!=null) { interval=newInterval(start.start, end.end); } elseif (start==null) { interval=newInterval(i_start, i_end); } if (start!=null) { intervals.remove(start); } if (end!=null) { intervals.remove(end); } for (inti=0; i<intervals.size(); i++) { if (intervals.get(i).start>interval.start) { intervals.add(i, interval); returnintervals; } } intervals.add(interval); returnintervals; } privatebooleanequals(Intervalstart, Intervalend) { if (start==null&&end==null) { returnfalse; } if (start==null||end==null) { returntrue; } if (start.start==end.start&&start.end==end.end) { returntrue; } returnfalse; }
时间复杂度：O（n）。
空间复杂度： O（1）。
总
总的来说，这道题可以看做上道题的一些变形，本质上是一样的。由于用 for 循环不能一边遍历列表，一边删除某个元素，所以利用迭代器实现边遍历，边删除，自己也是第一次用。此外，解法一更加通用些，它不要求给定的列表有序。
