首页 > 其他分享 >合并两个有序链表

合并两个有序链表

时间:2022-11-30 15:46:57浏览次数:37  
标签:ListNode 合并 next 链表 l2 有序 l1 null

21.合并两个有序链表

根据题目要求可以知道这两个链表是升序的,需要将这两个链表合成一个新的升序链表并返回

方法一:迭代

当 list1 和 list2 都不是空链表时,判断 list1 和 list2 哪一个链表的头结点的值更小,将较小值得结点添加到一个新的链表里,将对应链表中的结点向后移动一位即可

当其中一个链表为空时,结束循环,将不为空的链表接在后面即可

class Solution {
	public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode h = new ListNode(Integer.MAX_VALUE);
        ListNode t = h;

        while (l1 != null && l2 != null) {
        	if (l1.val < l2.val) {
            	t.next = l1;
                l1 = l1.next;
            } else {
            	t.next = l2;
                l2 = l2.next;
            }
            t = t.next;
        }

        t.next = l1 == null ? l2 : l1;
        return h.next;
    }
}

方法二:递归

class Solution {
    public 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;
        }
    }
}

标签:ListNode,合并,next,链表,l2,有序,l1,null
From: https://www.cnblogs.com/kingmc/p/16938629.html

相关文章

  • layui合并单元格
    在别人的基础上解决了多列合并和同一个页面多个表格的问题1//合并单元格2functionmerge(id,res,columsName,columsIndex){34var......
  • git的回退以及合并,删除什么的
    有时候不小心合并了别的分支中的commit.我们需要回退某些提交记录。可以通过reset来操作,reset会回退到指定commit。这种方式会删除记录,我们最好使用revert命令来操作git......
  • 链表基础知识
    1.什么是链表   链表是一种通过指针串联在一起的线性结构,每一个节点由两部分组成,一个是数据域一个是指针域(存放指向下一个节点的指针),最后一个节点的指针域指向null(空......
  • 双向链表
    双向链表介绍因为在循环链表中某一结点要访问其前驱结点的时候,需要循环扫描整个链表一遍,效率太低了。为了方便访问结点的前驱结点,我们引入了双向链表的概念。原本一个结......
  • bat脚本查找指定目录下的文件并将所有文件内容合并输出到一个文件里 写软著专用提取代
    1.将下面的代码复制到 并另存为【查找文件并合并内容.bat】里echooff&color0A::判断输入路径是不是文件夹,如果是,则获取文件夹下的所有文件名(包括子文件夹下的):......
  • 双链表
    //e[]表示节点的值,l[]表示节点的左指针,r[]表示节点的右指针,idx表示当前用到了哪个节点inte[N],l[N],r[N],idx;//初始化voidinit(){//0是左端点,1是右端点......
  • 链表-双向链表
    在双向链表中,除了下一个节点链接之外,每个节点还包含指向序列中“前一个”节点的第二个链接字段。这两个链接可以称为'forward('s')和'backwards',或'next'和'prev'('previous......
  • 相交链表
    160.相交链表由题目要求可以知道,题目数据保证了不会出现环形注意,函数返回结果后,链表必须保持其原始结构。方法一:哈希集合利用哈希表的特性,不能放重复元素判断两个链......
  • 【算法训练营day20】LeetCode654. 最大二叉树 LeetCode617. 合并二叉树 LeetCode700.
    LeetCode654.最大二叉树题目链接:654.最大二叉树初次尝试和昨天最后一题的思路很像,本质上都是递归构建二叉树。classSolution{public:TreeNode*constructMa......
  • 单向循环链表-约瑟夫问题
    单向环形列表应用场景:约瑟夫环问题思路:创建第一个节点,让first指向该节点,并形成环状后面当我们每创建一个新的节点,就把该节点,加入到已有的环形链表中即可遍历环形链......