【每天一道算法题】合并两个排序的链表

本专栏将会从基础开始，循序渐进，每天刷一道算法题，也请大家多多支持。数据结构虽然难，但只要肯坚持，一定能学好，希望大家都能够从中获益。
专栏地址: 每天一道算法题专栏 数据结构专栏
在线刷题网站：牛客网

准备好了吗
Let’s go!

前言

• 推荐给大家一款在线刷题神器，牛客网：刷题神器跳转链接
• 目前大厂的招聘都需要手撕代码，例如华为、腾讯等，该网站不仅可以在线编程模拟考试环境，熟悉考试流程，而且可以提升自己的代码能力与核心竞争力。
• 网站中不仅有算法入门及进阶教程，而且会将常见算法进行分类练习，例如链表篇、二叉树篇、堆/栈/队列以及递归和动态规划篇
• 除了刷算法题，还可以系统地学习其他知识，例如SQL篇、Python篇、HTML/CSS、JS篇、SHELL篇、名企真题、Verilog篇等，如下图所示：

Q1:反转链表

👀问题描述

题目来源:牛客网

✏️ 思路解析与题解
解法一，新建一个链表和一个哨兵节点（因为有去无回，需要哨兵节点来记录头节点的位置），遍历两个有序链表list1和list2，因为需要升序，那么谁小取谁做新链表的下一个节点，取谁的节点就往后移位，直到尾部null。

  public ListNode Merge(ListNode list1,ListNode list2) {
   

         if(list1==null){
   
             return list2;
         }

         if(list2==null){
   
             return list1;
         }
         ListNode result = new ListNode(-1);
         ListNode guard = result;//哨兵节点，很重要
         while(true){
   
             if(list1 == null && list2 == null){
   //全部取完了，可以结束了。
                 break;
             }
             if(list1==null){
   //list1取完了，后面的全部取list2的。
                 result.next = list2;
                 list2 = list2.next;
                 result = result.next;
             }else if(list2 == null){
   //list2取完了，后面全部取list1的。
                 result.next = list1;
                 list1 = list1.next;
                 result = result.next;
             }else if(list1.val<=list2.val){
   //和数组一样，谁小取谁的
                 result.next = list1;
                 list1 = list1.next;
                 result = result.next;
             }else if(list1.val>list2.val){
   //和数组一样，谁小取谁的
                 result.next = list2;
                 list2 = list2.next;
                 result = result.next;
             }
         }
         return guard.next;
     }


 

  
 

解法二，对解法一进行优化，观察到，如果想用尽一个链表，那么直接指向它的头节点就行了，省去解法一中，取剩余节点的步骤。

    public ListNode Merge(ListNode list1,ListNode list2) {
   

        if(list1==null){
   
            return list2;
        }

        if(list2==null){
   
            return list1;
        }
        ListNode result = new ListNode(-1);
        ListNode guard = result;
        while(list1!=null && list2!=null){
   

            if(list1.val<=list2.val){
   //同解法一
                result.next = list1;
                list1 = list1.next;
                result = result.next;
            }else if(list1.val>list2.val){
   //同解法一
                result.next = list2;
                list2 = list2.next;
                result = result.next;
            }
        }

        if(list1==null){
   //优化点，剩下的节点全部取list2
            result.next = list2;
        }

        if(list2==null){
   //优化点，剩下的节点全部取list1
            result.next = list1;
        }
        return guard.next;
    }
}

 

  
 

解法三， 使用递归，思想是：每次都取list1和list2的头节点进行比较，谁小谁当头节点，然后继续往后比较，这个步骤每一步都是一样的。

    public ListNode Merge(ListNode list1,ListNode list2) {
   

        //退出条件
        if(list1==null){
   
            return list2;
        }
        //退出条件
        if(list2==null){
   
            return list1;
        }

        ListNode guard = null;
        //谁小谁当头结点，然后继续重复这个步骤
        if(list1.val>=list2.val){
   
            guard = list2;
            guard.next = Merge(list1,list2.next);

        }else{
   
            guard = list1;
            guard.next = Merge(list1.next,list2);

        }
        return guard;
    }


 

  
 

点击如下链接进行跳转注册，开启你的从入门到精通的学习之路吧：
牛客网在线OJ

这里不仅有题库练习，而且包含面试和求职专区，在题库区中含有各个大公司的公司真题，如字节、腾讯、美团、阿里、百度、华为或者其他你想面试的公司，如下图所示：

在专项练习区中，你可以根据你的薄弱点进行针对性地练习，例如数组、字符串、链表、栈、队列、树、图、堆的题，如下图所示：

针对一些计算机基础知识，还涉及涉及模式、网络基础、数据库、操作系统等专项练习，让你巩固基础知识，在面试中侃侃而谈：

同时，还可以在线学习编程语言，免去配置环境的困扰，并且可以查漏补缺，早日收获大厂offer。