【第13题】合并两个有序链表(考察递归)

举报
小虚竹 发表于 2022/09/25 01:32:31 2022/09/25
【摘要】 回城传送–》《JAVA筑基100例》 文章目录 零、前言一、题目描述二、解题思路三、代码详解四、推荐专栏五、示例源码下载 零、前言 ​ 今天是学习 JAVA语言 打卡的第13天,每天我会提...

回城传送–》《JAVA筑基100例》

零、前言

​ 今天是学习 JAVA语言 打卡的第13天,每天我会提供一篇文章供群成员阅读( 不需要订阅付钱 ),读完文章之后,按解题思路,自己再实现一遍。在小虚竹JAVA社区 中对应的 【打卡贴】打卡,今天的任务就算完成了。

​ 因为大家都在一起学习同一篇文章,所以有什么问题都可以在群里问,群里的小伙伴可以迅速地帮到你,一个人可以走得很快,一群人可以走得很远,有一起学习交流的战友,是多么幸运的事情。

​ 学完后,自己写篇学习报告的博客,可以发布到小虚竹JAVA社区 ,供学弟学妹们参考。

​ 我的学习策略很简单,题海策略+ 费曼学习法。如果能把这100题都认认真真自己实现一遍,那意味着 JAVA语言 已经筑基成功了。后面的进阶学习,可以继续跟着我,一起走向架构师之路。

一、题目描述

原题地址–》传送门
题目:
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

在这里插入图片描述
在这里插入图片描述

二、解题思路

  • 如果把问题拆解成子问题,子问题具有跟父问题一样的结构,可以考虑用自上而下的递归
  • 对两个有序链接l1和l2进行判空处理,有空的话,返回另一个非空链接

三、代码详解

ListNode 链表对象

package com.xiaoxuzhu;

/**
 * Description: 链表对象
 *
 * @author zenghw
 * @version 1.0
 *
 * <pre>
 * 修改记录:
 * 修改后版本	        修改人		修改日期			修改内容
 * 2022/8/21.1	    zenghw		2022/8/21		    Create
 * </pre>
 * @date 2022/8/21
 */
public class ListNode {
    int val;
    ListNode next;

    public ListNode() {
        super();
    }

    public ListNode(int val) {
        this.val = val;
        this.next = null;
    }

    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

Solution类

package com.xiaoxuzhu;

/**
 * Description: 合并两个有序链表(考察递归)
 *
 * @author zenghw
 * @version 1.0
 *
 * <pre>
 * 修改记录:
 * 修改后版本	        修改人		修改日期			修改内容
 * 2022/8/21.1	    zenghw		2022/8/21		    Create
 * </pre>
 * @date 2022/8/21
 */
class Solution {
    public static void main(String[] args) {
        //l1 = [1,2,4], l2 = [1,3,4]
        //初始化数据
        int[] l1 = new int[]{1,2,4};
        int[] l2 = new int[]{1,3,4};
        //创建首节点,节点的val是1.
        ListNode listnode1 = new ListNode(1);
        //创建首节点,节点的val是1.
        ListNode listnode2 = new ListNode(1);    
        initListNode(listnode1,l1);
        initListNode(listnode2,l2);
        ListNode listnode3 =  mergeTwoLists(listnode1,listnode2);
        print(listnode3);
    }
    private static void print(ListNode listnode){
        //创建链表节点
        while(listnode!=null){
            System.out.println("节点:"+listnode.val);
            listnode=listnode.next;
        }
    }
    /**
     * 创建链表
     *
     * @param listnode 链表对象
     * @param arr 初始化数组数据
     *@return void
     **/
    public static void initListNode(ListNode listnode,int[] arr){
        //声明一个变量用来在移动过程中指向当前节点
        ListNode nextNode;
        //指向首节点,这样两个结点的指针指向同一个结点
        nextNode=listnode;                      
        //创建链表
        for (int i = 1; i < arr.length; i++) {
            //把新节点连起来
            nextNode.next= new ListNode(arr[i]);
            //当前节点往后移动
            nextNode=nextNode.next;           
        }
    }
    /**
     * 合并链表
     *
     * @param l1  要合并的链表1
     * @param l2 要合并的链表2
     *@return com.xiaoxuzhu.ListNode
     **/
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}


在这里插入图片描述

四、推荐专栏

《JAVA从零到壹》

《JAVA从零到壹》第七讲:面向对象高级特性

五、示例源码下载

关注下面的公众号,回复筑基+题目号

筑基13

文章来源: xiaoxuzhu.blog.csdn.net,作者:小虚竹,版权归原作者所有,如需转载,请联系作者。

原文链接:xiaoxuzhu.blog.csdn.net/article/details/126449945

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。