来，做一道字节跳动面试的简单算法题
面试大厂，算法基本是必面的，特别是字节跳动，技术面最后一个问题就是算法题，这次给大家带来一道字节跳动面试出的一道简单算法题。
请听题：
输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。并返回合并后的链表表头。
难度：简单
示例1：
输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4
限制：
0 <= 链表长度 <= 1000
请完成代码编写：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode head1, ListNode head2) {
//to do this
}
题目是这么个题目，看着不难，确实也不难的，只是如果没怎么接触过算法这一块，或者没怎么接触过链表的使用，其实一时还是不知道怎么入手比较好，大家可以看到这里，别往下看，先思考一下，看是否有思路，尝试自己写一下，看20分钟是否能比较好的完成这道题，做出来是一回事，既然是算法，还要关注它的时间复杂度和空间复杂度哦~
那实际上，稍微分析一下题目就很容易想到一种思路，两个链表都是递增的，要求合并它们，合并之后仍然是递增有序的，那我们可以逐个拿第二个链表的元素和第一个链表的元素取比较，找到一个合适的位置，插入到第一个链表中去，最后合并的链表就是第一个链表，然后再想办法找到第一个链表的表头返回即可。
话是这么说，但是实际写代码的时候，如果完全不引入变量的话，你会发现不是那么好处理，其实上面那个思路咱们可以稍微转换一下，那就是如果我有第三个链表head，然后我分别拿第一个链表head1的val和第二个链表head2的val比较，如果head1.val<head2.val，我就把head1放入到head里面去，然后再拿head1的下一个元素next的val去和刚刚的head2.val去比较，依然看谁大谁小，把小的放入head的下一个元素next中去，一直这样进行下去，知道head1或者head2遍历完成，剩下还没遍历完的就直接挂到head那个链表上去就好了。
好，大体思路相信大家都理解了，可以自己尝试一下。接下来咱们把思路步骤列出来并具体的代码给实现出来。
-
题目要求返回合并之后的表头，我们需要定义好一个虚拟表头head，因为如果不定义好，最后排完序我们的链表指针到尾部去了；
-
定义当前节点cur，初始化指向虚拟表头；
-
开始遍历head1和head2，循环条件是head1!=null && head2!=null；
-
比较head1.val和head2.val，哪个小，就把哪个元素赋值给cur.next，并把小的链表那个指针下移，当前节点也下移
-
剩余元素处理，最后看head1和head2那个链表还有剩余元素，因为它们不会同时遍历完，要么head1先遍历完，要么head2先遍历完，把没有遍历完的挂到cur的下一个元素即可，因为本身是有序的。
-
返回链表头节点，因为第一个节点是我们自己虚拟的，head.next才是我们合并完成之后的头节点。
看下面这个图更好理解：
代码实现
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
class Solution {
public ListNode mergeTwoLists(ListNode head1, ListNode head2) {
//to do this
//1、定义好一个虚拟节点，初始值可设置为0
ListNode head = new ListNode(0);
//2、定义一个链表来放head1和head1的元素，初始值就等于head
ListNode cur = head;
//3、遍历head1和head2
while(head1!=null && head2!=null){
//4、比较head1.val和head2.val，哪个小，就把哪个元素赋值给cur.next，并把小的链表那个指针下移
if(head1.val<=head2.val){
cur.next = head1;
head1 = head1.next;
}else{
cur.next = head2;
head2 = head2.next;
}
//当前节点也下移
cur = cur.next;
}
//5、剩余元素处理
cur.next = head1==null ? head2:head1;
//6、返回链表头节点
return head.next;
}
//测试一下
public static void main(String[] args){
//构建两个链表
ListNode l1 = new ListNode(1);
l1.next = new ListNode(2);
l1.next.next = new ListNode(4);
ListNode l2 = new ListNode(1);
l2.next = new ListNode(3);
l2.next.next = new ListNode(4);
ListNode head = new Solution().mergeTwoLists(l1,l2);
StringBuilder sb = new StringBuilder();
while(head!=null){
sb.append(head.val);
head = head.next;
if(head!=null){
sb.append("->");
}
}
System.out.println(sb.toString());
}
}
输出结果：
1->1->2->3->4->4
复杂度分析： 时间复杂度 O(M+N)：M,N 分别为链表的长度，合并操作需遍历两链表。 空间复杂度O(1) ： 节点引用 head , cur使用常数大小的额外空间。
所有总体效果还是不错的，至少时间复杂度不是O(N^2)，是一个线性阶，也只额外引入一个节点引用。
你做出来了吗？可能大家都做出来了，或许比我这个实现更好~
这里顺便给大家推荐两个学习算法的网站：
好了，本次内容就是这些，学无止境，关注我，我们一起进步。创作整理不容易，球球大家点个在看吧，谢谢~我们下期见。