算法-合并两个有序链表

分手后的思念是犯贱 2024-04-18 07:34 69阅读 0赞

## 1. 合并两个有序链表 ##

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4  
输出：1->1->2->3->4->4

链接：[leetcode 原题][leetcode]

## 2. 解法 ##

#### 2.1 递归 ####

递归方式逐个比较两链表元素值，一次递归确定新链表的一个元素

public ListNode merge(ListNode list1, ListNode list2) {
        
            if (list1 == null) return list2;
            if (list2 == null) return list1;
    
            ListNode p = null;
            if (list1.val < list2.val) {
        
                p = list1;
                p.next = merge(list1.next, list2);
            } else {
        
                p = list2;
                p.next = merge(list1, list2.next);
            }
            return p;
        }

#### 2.2 非递归 ####

使用额外节点记录新链表中加入的元素，逐步移动并加入下一个元素

public ListNode merge(ListNode list1, ListNode list2) {
        
            ListNode prehead = new ListNode(-1);
            ListNode prev = prehead;
            while (l1 != null && l2 != null) {
        
                if (l1.val <= l2.val) {
        
                    prev.next = l1;
                    l1 = l1.next;
                } else {
        
                    prev.next = l2;
                    l2 = l2.next;
                }
                prev = prev.next;
            }
            prev.next = l1 == null ? l2 : l1; // 两链表长度不同
            return prehead.next;
        }

[leetcode]: https://leetcode-cn.com/problems/merge-two-sorted-lists

发表评论取消回复

表情：

评论列表（有 0 条评论，69人围观）

还没有评论，来说两句吧...

相关阅读

相关算法-合并两个有序链表

1. 合并两个有序链表将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例：输入：1->2->4, 1->3->...

分手后的思念是犯贱/ 2024年04月18日 07:34/ 0 赞/ 70 阅读

相关 [算法专题 ] 合并两个有序链表

目录描述: 效果: 思路: 代码: 链表虚拟节点尾节点 -------------------- 描述: > 将两个升序链表合并为一个新的升序

快来打我*/ 2023年09月30日 14:23/ 0 赞/ 5 阅读

相关合并两个有序链表

一思路按老师上课讲的，先用其他链表记录两个链表共有部分，然后判断谁null，再接上另一个二代码 class Solution(object):

爱被打了一巴掌/ 2023年07月13日 10:51/ 0 赞/ 10 阅读

相关合并两个有序链表

合并两个有序链表 1、题目题目要求：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例：输

灰太狼/ 2023年03月01日 12:52/ 0 赞/ 9 阅读

相关 leetcode算法题--合并两个有序链表

题目概述 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLm

末蓝、/ 2022年11月26日 01:44/ 0 赞/ 175 阅读

相关链表----21. 合并两个有序链表

【题目】将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例 1： ![在这里插入图片描述][watermark_typ

「爱情、让人受尽委屈。」/ 2022年11月16日 01:54/ 0 赞/ 223 阅读

相关合并两个链表c++_21 合并两个有序链表

01 题目信息 > 题目地址: > > https://leetcode-cn.com/problems/merge-two-sorted-lists/

朴灿烈づ我的快乐病毒、/ 2022年10月25日 04:52/ 0 赞/ 221 阅读

相关算法：合并两个有序链表

1. 题目：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 e.g 输入：l1 = \[1,2,5\], l2 =

雨点打透心脏的1/2处/ 2022年10月14日 05:53/ 0 赞/ 212 阅读

相关合并两个有序链表

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

向右看齐/ 2022年09月01日 12:56/ 0 赞/ 233 阅读

相关合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例：输入：1->2->4, 1->3->4

我会带着你远行/ 2021年10月30日 08:20/ 0 赞/ 350 阅读