【LintCode 简单】165. 合并两个排序链表

小灰灰 2022-06-01 04:08 190阅读 0赞

1.问题描述：

将两个排序链表合并为一个新的排序链表。

2.样例:

给出 `1->3->8->11->15->null`，`2->null`， 返回 `1->2->3->8->11->15->null`。

3.代码：

"""
    Definition of ListNode
    class ListNode(object):
        def __init__(self, val, next=None):
            self.val = val
            self.next = next
    """
    
    
    class Solution:
        """
        @param: l1: ListNode l1 is the head of the linked list
        @param: l2: ListNode l2 is the head of the linked list
        @return: ListNode head of linked list
        """
        def mergeTwoLists(self, l1, l2):
            # write your code here
            if l1 is None:
                return l2
            elif l2 is None:
                return l1
            else:
                if l1.val <= l2.val:
                    newhead=p=l1
                    l1=l1.next
                else:
                    newhead=p=l2
                    l2=l2.next
                    
                while l1 and l2: 
                    if l1.val <= l2.val:
                        p.next=l1
                        l1=l1.next
                        p=p.next
                    else:
                        p.next=l2
                        l2=l2.next
                        p=p.next
                if l1:
                    p.next=l1
                if l2:
                    p.next=l2
            return newhead

本题思路并不复杂，代码看起来稍有点多。主要分为几种情况：

1）l1或l2中如果有None，则直接返回另外一个链表即可

2）需要判断两个链表的头结点的大小，确定新链表的头结点

3）当某个链表的数已经全部加到新链表中后，把另外一个链表剩余的数加入即可

发表评论取消回复

表情：

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

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

相关阅读

相关合并两个排序的链表

文章目录题目描述代码题目描述输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。代码

Dear 丶/ 2024年02月19日 13:38/ 0 赞/ 63 阅读

相关 lintcode 104. 合并k个排序链表优先队列

合并k个排序链表，并且返回合并后的排序链表。尝试分析和描述其复杂度。样例样例 1: 输入: [2->4->null,null,-1->nul

傷城~/ 2023年07月03日 07:08/ 0 赞/ 12 阅读

相关合并两个排序的链表

时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M 热度指数：899289 题目描述输入两个单调递增的链表，输出两个链表合成后的

蔚落/ 2023年01月13日 09:49/ 0 赞/ 239 阅读

相关合并两个排序的链表

class Solution { / 递归的方式依次比较 / public ListNode mergeTwoLists(ListN

朴灿烈づ我的快乐病毒、/ 2022年10月30日 05:22/ 0 赞/ 184 阅读

相关【链表】合并两个排序的链表

First \------ 递归思路，需要重新创建一个链表，空间复杂度O(1) ListNode Merge(ListNode pHead1, ListNode p

绝地灬酷狼/ 2022年09月25日 11:28/ 0 赞/ 214 阅读

相关合并两个排序的链表

题目描述输入两个单调递增的链表，输出两个链表合并后的链表，当然我们需要合并后的链表满足单调不减规则。方法一，非递归，循环比较两个节点的大小 / pub

叁歲伎倆/ 2022年06月08日 01:11/ 0 赞/ 208 阅读

相关【LintCode 简单】165. 合并两个排序链表

1.问题描述：将两个排序链表合并为一个新的排序链表。 2.样例: 给出 `1->3->8->11->15->null`，`2->null`，返回 `1->2->

小灰灰/ 2022年06月01日 04:08/ 0 赞/ 191 阅读

相关合并两个排序的链表

![这里写图片描述][70] class ListNode { int val; ListNode next = null;

绝地灬酷狼/ 2022年05月26日 13:36/ 0 赞/ 203 阅读

相关链表问题_合并两个排序链表

题目：输入两个递增排序的链表，合并这两个排序链表，使得合并之后的链表仍然使递增排序的。分析：即是归并排序中的归并操作，有两种具体的实现：1、使用递归的方法，2、迭代版本，

╰+哭是因爲堅強的太久メ/ 2022年05月21日 01:57/ 0 赞/ 227 阅读

相关合并两个排序的链表

时间限制：1秒空间限制：32768K 热度指数：390585 本题知识点：链表算法知识视频讲解题目描述输入两个单调递增的链表，输出两个链表合成后的链表

深碍√TFBOYSˉ_/ 2022年03月10日 01:37/ 0 赞/ 229 阅读