# 区间合并算法
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]
算法描述：
第一步，必须先排序，根据区间的起始start来排序。
第二部，当我们有了有序的区间集合后，就可以遍历每个区间。定义待入队的基准区间（最开始为第一个区间），并且比较目前遍历到的区间的start是否小于等于待入队基准区间end。如果是，那这两个区间可以合并了，修改基准区间的end。否则，这个待入队的基准区间可以直接加入结果队列，然后更新待入队基准区间为刚遍历的区间。
## 链表算法
如何找到链表的中间元素？
我们可以采用快慢指针的思想，使用步长为1的慢指针和步长为2的快指针，当快指针抵达链表末尾时，此时慢指针指向的即为中点位置。
我们还可以采用递归的方式，当递归到最末尾的时候，我们已经能知道链表的长度，此时当递归回去的时候，判断当前递归层级等于链表长度一半的时候，即为链表的重点。
2.检测链表是否有环。
检测链表是否有环是非常常见的算法考察。常见的就是使用快慢指针，如果快慢指针有重合的时候，说明链表是有环的。
3.如何列表反转（递归）
我们可以在递归回溯的时候，反向更改节点的指针。
public static void reverseLinkListByRecursion(LinkNode cur, LinkNode next) {
if (next == null) {
return;
}
reverseLinkListByRecursion(next, next.next);
next.next = cur;
cur.next = null;
return;
}
4.如何反转链表（非递归）
反转链表的非递归方式，我们可以采用三个指针，分别指向当前节点，下个节点，下下个节点，调整好下个节点的next指向后，继续利用下下个节点进行往后操作。
5.删除经过排序的链表中重复的节点。
通过在遍历中，判断当前的数字是否与之前的重复数字相同，如果相同的话，直接跳过，直到找到与之前重复数字不同时，将原先的指针跳过重复的节点，指向当前非重复数字节点。
6.如何计算两个链表的代表数字之和。
将链表代表的数字进行相加即可，注意首位代表的是个位。3->1->5 代表513，5->9->2 代表295，最终计算结果为 8->0->8， 808。
7.链表-奇数位升序偶数位降序-让链表变成升序
先将链表拆分成奇数的链表，和偶数的链表，然后翻转偶数的链表，在合并两个链表。
8.一个单向链表，删除倒数第N个数据。
准备两个指针，初始指向头结点，1号指针先走n步，然后2号指针开始走，当1号指针走到尾节点时，2号指针即为倒数第N个数据。
题目：输入一个单链表，输出此链表中的倒数第 K 个节点。（去除头结点，节点计数从 1 开始）。
两次遍历法
1）遍历单链表，遍历同时得出链表长度 N 。
2）再次从头遍历，访问至第 N - K 个节点为所求节点。
递归法
1）定义num = k
2）使用递归方式遍历至链表末尾。
3）由末尾开始返回，每返回一次 num 减 1
4）当 num 为 0 时，即可找到目标节点
int num;//定义num值
ListNode* findKthTail(ListNode* pHead, int k) {
num = k;
if(pHead == NULL)
return NULL;
//递归调用
ListNode* pCur = findKthTail(pHead->next, k);
if(pCur != NULL)
return pCur;
else{
num--;// 递归返回一次，num值减1
if(num == 0)
return pHead;//返回倒数第K个节点
return NULL;
}
}
双指针法
1）定义两个指针 p1 和 p2 分别指向链表头节点。
2）p1 前进 K 个节点，则 p1 与 p2 相距 K 个节点。
3）p1，p2 同时前进，每次前进 1 个节点。
4）当 p1 指向到达链表末尾，由于 p1 与 p2 相距 K 个节点，则 p2 指向目标节点。
题目：判断链表是否有环
穷举比较法
1）遍历链表，记录已访问的节点。
2）将当前节点与之前以及访问过的节点比较，若有相同节点则有环。
否则，不存在环。
哈希缓存法
1）首先创建一个以节点 ID 为键的 HashSe t集合，用来存储曾经遍历过的节点。
2）从头节点开始，依次遍历单链表的每一个节点。
3）每遍历到一个新节点，就用新节点和 HashSet 集合当中存储的节点作比较，如果发现 HashSet 当中存在相同节点 ID，则说明链表有环，如果 HashSet 当中不存在相同的节点 ID，就把这个新节点 ID 存入 HashSet ，之后进入下一节点，继续重复刚才的操作。
