来，做一道字节跳动面试的简单算法题

面试大厂，算法基本是必面的，特别是字节跳动，技术面最后一个问题就是算法题，这次给大家带来一道字节跳动面试出的一道简单算法题。

请听题：

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。并返回合并后的链表表头。

难度：简单

示例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那个链表上去就好了。

好，大体思路相信大家都理解了，可以自己尝试一下。接下来咱们把思路步骤列出来并具体的代码给实现出来。

1. 题目要求返回合并之后的表头，我们需要定义好一个虚拟表头head，因为如果不定义好，最后排完序我们的链表指针到尾部去了；
2. 定义当前节点cur，初始化指向虚拟表头；
3. 开始遍历head1和head2，循环条件是head1!=null && head2!=null；
4. 比较head1.val和head2.val，哪个小，就把哪个元素赋值给cur.next，并把小的链表那个指针下移，当前节点也下移
5. 剩余元素处理，最后看head1和head2那个链表还有剩余元素，因为它们不会同时遍历完，要么head1先遍历完，要么head2先遍历完，把没有遍历完的挂到cur的下一个元素即可，因为本身是有序的。
6. 返回链表头节点，因为第一个节点是我们自己虚拟的，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)，是一个线性阶，也只额外引入一个节点引用。

你做出来了吗？可能大家都做出来了，或许比我这个实现更好~

这里顺便给大家推荐两个学习算法的网站：

力扣：https://leetcode-cn.com/

牛客网：https://www.nowcoder.com/