为了巩固基础算法能力，同时也为了在面试中可以做到心中有数，我通过刷题的方式让自己保持头脑清醒，让自己对基础算法题目时刻保持感觉。
我几乎每天都通过刷题的方式让自己保持清醒，最近也感觉自己算法能力又明显的提升，所以说，这样的方式是可行的！希望我的刷题笔记能够帮助到大家，接下来让我们一起开始算法之旅吧。
第一题: 合并两个排序的链表
1. 题目描述
输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。
数据范围： 0 ≤n≤ 1000，−1000≤节点值≤1000
要求：空间复杂度 O(1)，时间复杂度 O(n)
如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，所以对应的输出为{1,2,3,4,5,6}，转换过程如下图所示：
或输入{-1,2,4},{1,3,4}时，合并后的链表为{-1,1,2,3,4,4}，所以对应的输出为{-1,1,2,3,4,4}，转换过程如下图所示：
2. 示例
示例1
输入： {1,3,5},{2,4,6}
返回值： {1,2,3,4,5,6}
示例2
输入：{},{}
返回值：{}
示例3
输入： {-1,2,4},{1,3,4}
返回值： {-1,1,2,3,4,4}
3. 个人思路分析
(1) 创建额外存储数组 nums
(2) 依次循环遍历 pHead1, pHead2，将链表中的元素存储到 nums中，再对nums进行排序
(3) 依次对排序后的数组 nums取数并构建合并后的链表
4. 题解
Java代码实现：
public class Solution { public ListNode Merge(ListNode list1,ListNode list2) { // list1 list2为空的情况 if(list1==null) return list2; if(list2==null) return list1; if(list1 == null && list2 == null){ return null; } //将两个两个链表存放在list中 ArrayList<Integer> list = new ArrayList<>(); // 遍历存储list1 while(list1!=null){ list.add(list1.val); list1 = list1.next; } // 遍历存储list2 while(list2!=null){ list.add(list2.val); list2 = list2.next; } // 对 list 排序 Collections.sort(list); // 将list转换为 链表 ListNode newHead = new ListNode(list.get(0)); ListNode cur = newHead; for(int i=1;i<list.size();i++){ cur.next = new ListNode(list.get(i)); cur = cur.next; } // 输出合并链表 return newHead; } }
第二题：合并k个已排序的链表
1. 题目描述
合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。
数据范围：节点总数 0 ≤n≤ 5000，每个节点的val满足 ∣val∣<=1000
要求：时间复杂度 O(nlogn)
2. 示例
示例1
输入： [{1,2,3},{4,5,6,7}]
返回值： {1,2,3,4,5,6,7}
示例2
输入： [{1,2},{1,4,5},{6}]
返回值： {1,1,2,4,5,6}
3. 个人思路分析
如果是两个有序链表合并，我们可能会利用归并排序合并阶段的思想：准备双指针分别放在两个链表头，每次取出较小的一个元素加入新的大链表，将其指针后移，继续比较，这样我们出去的都是最小的元素，自然就完成了排序。
其实这道题我们也可以两两比较啊，只要遍历链表数组，取出开头的两个链表，按照上述思路合并，然后新链表再与后一个继续合并，如此循环，知道全部合并完成。但是，这样太浪费时间了。
既然都是归并排序的思想了，那我们可不可以直接归并的分治来做，而不是顺序遍历合并链表呢？答案是可以的！
归并排序是什么？简单来说就是将一个数组每次划分成等长的两部分，对两部分进行排序即是子问题。对子问题继续划分，直到子问题只有1个元素。还原的时候呢，将每个子问题和它相邻的另一个子问题利用上述双指针的方式，1个与1个合并成2个，2个与2个合并成4个，因为这每个单独的子问题合并好的都是有序的，直到合并成原本长度的数组。
对于这k个链表，就相当于上述合并阶段的k个子问题，需要划分为链表数量更少的子问题，直到每一组合并时是两两合并，然后继续往上合并，这个过程基于递归：
- 终止条件： 划分的时候直到左右区间相等或左边大于右边。
- 返回值： 每级返回已经合并好的子问题链表。
- 本级任务： 对半划分，将划分后的子问题合并成新的链表。
4. 题解
Java代码实现：
import java.util.ArrayList; public class Solution { //两个链表合并函数 public ListNode Merge(ListNode list1, ListNode list2) { //一个已经为空了，直接返回另一个 if(list1 == null) return list2; if(list2 == null) return list1; //加一个表头 ListNode head = new ListNode(0); ListNode cur = head; //两个链表都要不为空 while(list1 != null && list2 != null){ //取较小值的节点 if(list1.val <= list2.val){ cur.next = list1; //只移动取值的指针 list1 = list1.next; }else{ cur.next = list2; //只移动取值的指针 list2 = list2.next; } //指针后移 cur = cur.next; } //哪个链表还有剩，直接连在后面 if(list1 != null) cur.next = list1; else cur.next = list2; //返回值去掉表头 return head.next; } //划分合并区间函数 ListNode divideMerge(ArrayList<ListNode> lists, int left, int right){ if(left > right) return null; //中间一个的情况 else if(left == right) return lists.get(left); //从中间分成两段，再将合并好的两段合并 int mid = (left + right) / 2; return Merge(divideMerge(lists, left, mid), divideMerge(lists, mid + 1, right)); } public ListNode mergeKLists(ArrayList<ListNode> lists) { //k个链表归并排序 return divideMerge(lists, 0, lists.size() - 1); } }
第三题：判断链表中是否有环
1. 题目描述
判断给定的链表中是否有环。如果有环则返回true，否则返回false。
数据范围：链表长度 0≤n≤10000，链表中任意节点的值满足 ∣val∣<=100000
要求：空间复杂度 O(1)，时间复杂度 O(n)
输入分为两部分，第一部分为链表，第二部分代表是否有环，然后将组成的head头结点传入到函数里面。-1代表无环，其它的数字代表有环，这些参数解释仅仅是为了方便读者自测调试。实际在编程时读入的是链表的头节点。
例如输入{3,2,0,-4},1时，对应的链表结构如下图所示：
可以看出环的入口结点为从头结点开始的第1个结点（注：头结点为第0个结点），所以输出true。
2. 示例
示例1
输入： {3,2,0,-4},1
返回值： true
说明：第一部分{3,2,0,-4}代表一个链表，第二部分的1表示，-4到位置1（注：头结点为位置0），即-4->2存在一个链接，组成传入的head为一个带环的链表，返回true
示例2
输入： {1},-1
返回值： false
说明：第一部分{1}代表一个链表，-1代表无环，组成传入head为一个无环的单链表，返回false
示例3
输入： {-1,-7,7,-4,19,6,-9,-5,-2,-5},6
返回值： true
3. 个人思路分析
我们都知道链表不像二叉树，每个节点只有一个val值和一个next指针，也就是说一个节点只能有一个指针指向下一个节点，不能有两个指针，那这时我们就可以说一个性质：环形链表的环一定在末尾，末尾没有NULL了。为什么这样说呢？仔细看上图，在环2，0，-4中，没有任何一个节点可以指针指出环，它们只能在环内不断循环，因此环后面不可能还有一条尾巴。如果是普通线形链表末尾一定有NULL，那我们可以根据链表中是否有NULL判断是不是有环。
但是，环形链表遍历过程中会不断循环，线形链表遍历到NULL结束了，但是环形链表何时能结束呢？我们可以用双指针技巧，同向访问的双指针，速度是快慢的，只要有环，二者就会在环内不断循环，且因为有速度差异，二者一定会相遇。
4. 题解
Java代码实现：
public class Solution { public boolean hasCycle(ListNode head) { //先判断链表为空的情况 if(head == null) return false; //快慢双指针 ListNode fast = head; ListNode slow = head; //如果没环快指针会先到链表尾 while(fast != null && fast.next != null){ //快指针移动两步 fast = fast.next.next; //慢指针移动一步 slow = slow.next; //相遇则有环 if(fast == slow) return true; } //到末尾则没有环 return false; } }
