【数据结构】链表：LeetCode题（三）21.合并两个有序链表

女爷i 2022-11-03 00:48 136阅读 0赞

## [21. 合并两个有序链表¹][21.] ##

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

**示例：**

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

### 解法一：双指针（归并） ###

*  思路：新建一个头，链表1，链表2比大小插入即可。就像归并排序中合并两个子数组一样。  
    注：这里能这么做的前提一定是待合并的两部分是排好序的！！
 *  复杂度
    
     *  Time：O（m + n）
     *  Space：O（1)

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        
        	// 创建一个虚拟头结点
            ListNode head = new ListNode(0), p = head;
            while (l1 != null && l2 != null) {
        
                if (l1.val < l2.val) {
        
                    p.next = l1;
                    l1 = l1.next;
                } else {
        
                    p.next = l2;
                    l2 = l2.next;
                }
                p = p.next;
            }
        	// 可能还存在一个链表未遍历完的情况
            if (l1 != null) p.next = l1;
            if (l2 != null) p.next = l2;
    		// 注：这里要返回head.next，因为head是我们new的虚拟头结点
            return head.next;
        }

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

发表评论取消回复

表情：

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

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

相关阅读

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

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

短命女/ 2024年02月20日 13:13/ 0 赞/ 200 阅读

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

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

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

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

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

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

相关【数据结构】链表：LeetCode题（三）21.合并两个有序链表

[21. 合并两个有序链表¹][21.] 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例：输入：1-

女爷i/ 2022年11月03日 00:48/ 0 赞/ 137 阅读

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

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

心已赠人/ 2022年09月15日 03:29/ 0 赞/ 209 阅读

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

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

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

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

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

蔚落/ 2022年04月23日 16:10/ 0 赞/ 232 阅读

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

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

客官°小女子只卖身不卖艺/ 2022年04月18日 02:07/ 0 赞/ 275 阅读

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

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

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

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

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

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