[leetcode] 合并两个有序链表

柔光的暖阳◎ 2023-06-13 09:51 9阅读 0赞

## 题目 ##

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

示例：

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

## 思路 ##

将两个有序的序列合并成一个有序的序列,可以使用归并的思想.  
类似于小学老师安排学生排队,男生一排依次从矮到高,女生一排依次从矮到高,每次比较男生和女生两排的排首同学身高,矮的那位排到新的队列末尾,不断循环最终可以得到一条合并了男生女生的依次从矮到高的队列.

## 解题 ##

class Solution { 
     public ListNode mergeTwoLists(ListNode l1, ListNode l2) { 
        if (l2 == null) return l1;
        if (l1 == null) return l2;
        ListNode p1 = l1;
        ListNode p2 = l2;
        ListNode start = l1.val < l2.val ? l1 : l2;
        do { 
            if (p2.val <= p1.val) { 
                while (p2.next != null && p2.next.val <= p1.val) { 
                    p2 = p2.next;
                }
                l2 = p2.next;
                p2.next = p1;
            } else { 
                while (p1.next != null && p1.next.val < p2.val) { 
                    p1 = p1.next;
                }
                l2 = p2.next;
                p2.next = p1.next;
                p1.next = p2;
            }
            p2 = l2;
        } while (p2 != null);
        return start;
    }
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 [leetcode] 合并两个有序链表

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

柔光的暖阳◎/ 2023年06月13日 09:51/ 0 赞/ 10 阅读

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

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

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

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

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

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

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

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

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

相关 LeetCode 合并两个有序链表

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

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

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

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

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

相关 Leetcode 合并两个有序链表

问题描述 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3

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

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

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

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

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

Java code class Solution { public ListNode mergeTwoLists(ListNod

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

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

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

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