Leetcode 合并两个有序链表

约定不等于承诺〃 2022-03-16 00:42 277阅读 0赞

问题描述

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5NTUwMA_size_16_color_FFFFFF_t_70][]

先上代码：

/\*\*  
 \* Definition for singly-linked list.  
 \* public class ListNode \{  
 \*     int val;  
 \*     ListNode next;  
 \*     ListNode(int x) \{ val = x; \}  
 \* \}  
 \*/  
class Solution \{  
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) \{  
        //类似归并排序，哪个空了，就把剩下那串补上  
        if (l1 == null) return l2;  
        if (l2 == null) return l1;  
        ListNode head = null;  
        if (l1.val <= l2.val) \{  
            head = l1;  
            head.next = mergeTwoLists(l1.next, l2);    
        \} else \{  
            head = l2;  
            head.next = mergeTwoLists(l1, l2.next);  
        \}  
        return head;  
    \}  
\}

解析：

这其实就是在考察归并排序，先判断两个链表的表头，取出较小者作为新链表的元素，对应的链表指针后移，然后不断重复这个过程直到有一个链表被取空。取空之后再判断一下被取空的是哪一个链表，把剩下那一串补上就行。本题巧妙的地方在于可以写成递归形式，简洁而优雅。

时间复杂度：

O( m + n)，与两个链表的长度之和成正比

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5NTUwMA_size_16_color_FFFFFF_t_70]: /images/20220316/4052f41f694f44e9b3bfa69638b14b64.png

发表评论取消回复

表情：

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

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

相关阅读

相关【链表】 LeetCode21. 合并两个有序链表

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

一时失言乱红尘/ 2022年12月02日 13:38/ 0 赞/ 154 阅读

相关 LeetCode 21. 合并两个有序链表（链表）

上一篇博客：[LeetCode 20. 有效的括号（栈、字符串）][LeetCode 20.] > 写在前面：大家好！我是`ACfun`,我的昵称来自两个单词`Accept

左手的ㄟ右手/ 2022年11月28日 13:51/ 0 赞/ 229 阅读

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

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

╰半橙微兮°/ 2022年09月12日 14:57/ 0 赞/ 209 阅读

相关 LeetCode 合并两个有序链表

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

以你之姓@/ 2022年09月11日 15:28/ 0 赞/ 239 阅读

相关 LeetCode21. 合并两个有序链表

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

清疚/ 2022年05月26日 04:29/ 0 赞/ 237 阅读

相关 Leetcode 合并两个有序链表

问题描述 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3

约定不等于承诺〃/ 2022年03月16日 00:42/ 0 赞/ 278 阅读

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

github：[https://github.com/Renhongqiang/LeetCode][https_github.com_Renhongqiang_LeetCode

Love The Way You Lie/ 2022年02月15日 11:46/ 0 赞/ 255 阅读

相关 LeetCode(合并两个有序链表)

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

ゝ一世哀愁。/ 2022年02月03日 13:27/ 0 赞/ 298 阅读

相关【LeetCode】合并两个有序链表

Java code class Solution { public ListNode mergeTwoLists(ListNod

以你之姓@/ 2021年11月01日 16:22/ 0 赞/ 340 阅读

相关 Leetcode21. 合并两个有序链表

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

超、凢脫俗/ 2021年09月27日 00:08/ 0 赞/ 348 阅读